堆栈应用之表达式优先级

带优先级的计算器实现

#include <iostream>
using namespace std;


#define size 100

typedef struct Char//运算符栈结构
{
	char data[size];
	int top;
}CHAR;

typedef struct Num//操作数栈结构
{
	double data[size];
	int top;
}NUM;

void InitC(CHAR* C)//初始化运算符栈
{
	C->top = -1;
}
void InitN(NUM* N)//初始化操作数栈
{
	N->top = -1;
}
void PushC(CHAR* C, char e)//运算符压栈
{
	C->data[++C->top] = e;
}
void PushN(NUM* N, double e)//操作数压栈
{
	N->data[++N->top] = e;
}
char PopC(CHAR* C)//运算符出栈
{
	return C->data[C->top--];
}
double PopN(NUM* N)//操作数出栈
{
	return N->data[N->top--];
}
double GetTopN(NUM* N)//取操作数栈顶元素
{
	return N->data[N->top];
}
char GetTopC(CHAR* C)//取运算符栈顶元素
{
	return C->data[C->top];
}

//判断输入的字符串是否正确
bool fun(char* str)
{
	int x = 0, i = 0;
	while (*str) {
		if ((*str < '0' || *str > '9') && *str != '+' && *str != '-' //不是数字+-*/（）则false
			&& *str != '*' && *str != '/' && *str != '(' && *str != ')') {
			return false;
		}
		if ((i == 0) && (*str < '0' || *str > '9') && *str != '(') { //开头不为（ 或数字 则false
			return false;
		}
		if (((*str >= '0' && *str <= '9') || *str == ')') && (*(str + 1) == '(')) {
			return false; //如果是数字和 ），后面是 （ 则false
		}
		if (*str == ')') { //如果是 ） ，
			x--;
			if (x < 0) {
				return false;
			}
		}
		if ((*str == '+' || *str == '-' || *str == '*' || *str == '/' || *str == '(') &&
			(*(str + 1) == 0 || *(str + 1) == '+' || *(str + 1) == '-' || *(str + 1) == '*' || *(str + 1) == '/' || *(str + 1) == ')')) {
			return false; //如果是运算符号 ，后面不能是运算符号和 ）
		}
		if (*str == '(') { //如果是 （
			x++;
		}
		str++; i++;
	}
	if (x > 0) { //如果括号不匹配
		return false;
	}
	return true;
}

int op(char ch)//判断字符是否为运算符
{
	char a[8] = { '+', '-', '*', '/', '(', ')', '=','#' };
	int i;
	for (i = 0; i < 8; i++)
	{
		if (ch == a[i])
			return 1;
	}
	return 0;
}

double operate(double a, char op, double b)//执行运算
{
	switch (op)
	{
	case '+':return a + b; break;
	case '-':return a - b; break;
	case '*':return a * b; break;
	case '/':return a / b; break;
	default:return 0; break;
	}
}

char compare(char a, char b)//比较运算符优先级
{
	int i, j;
	char Table[8][8] =
	{
	{ ' ', '+', '-', '*', '/', '(', ')', '#'},
	{ '+', '>', '>', '<', '<', '<', '>', '>'},
	{ '-', '>', '>', '<', '<', '<', '>', '>'},
	{ '*', '>', '>', '>', '>', '<', '>', '>'},
	{ '/', '>', '>', '>', '>', '<', '>', '>'},
	{ '(', '<', '<', '<', '<', '<', '=', ' '},
	{ ')', '>', '>', '>', '>', ' ', '>', '>'},
	{ '#', '<', '<', '<', '<', '<', ' ', '='},
	
	};  //优先级对照表
	for (i = 0; i < 8; i++)
		if (Table[i][0] == a)  //寻找a的位置
			break;
	for (j = 0; j < 8; j++)  //寻找b的位置
		if (Table[0][j] == b)
			break;
	return Table[i][j];
}

int main() {
	char ch[100];
	
	cout << "请输入要计算的表达式：";
	cin >> ch;
	//输入字符串
	
	int len = 0;
	//获取表达式长度
	len = strlen(ch);
	//表达式末尾加一个‘#’
	
	if (fun(ch) == 1) { cout << "输入的表达式正确"<<endl; }
	else{ cout << "输入的表达式错误" << endl; }

	ch[len] = '#';

	double a, b;

	char theta;//运算符
	//初始化操作数栈和运算符栈
	NUM OPND;
	CHAR OPTR;
	InitC(&OPTR);
	InitN(&OPND);
	PushC(&OPTR, '#');

	int i = 0;

	while (ch[i] != '#' || GetTopC(&OPTR) != '#')
	{

		if (!op(ch[i])) {
			double num = 0;
			int j = 0;

			while (ch[i] >= '0' && ch[i] <= '9' || ch[i] == '.') { //把字符串换算成实际数值
				if (ch[i] != '.')num = num * 10 + ch[i] - '0';
				if (ch[i] == '.' || j > 0) j++;
				i++;
			}
			//对小数进行额外处理
			if (j > 0) num = num / pow(10, j - 1);
			PushN(&OPND, num);
		}

		if (op(ch[i]))

		{
			


				switch (compare(GetTopC(&OPTR), ch[i]))
				{
				case'<':PushC(&OPTR, ch[i]);
					i++;
					break;
				case'=':PopC(&OPTR);
					i++;
					break;
				case'>':theta = PopC(&OPTR);					
						b = PopN(&OPND); a = PopN(&OPND);
						PushN(&OPND, operate(a, theta, b));					
					   break;
				}
			
		}



	}
	cout << "运算结果为："<<GetTopN(&OPND);
	return 0;
}