本章内容使用上述栈结构函数，来完成表达式求值操作。
表达式例如：3*(7-2) 或者 (0-12)*((5-3)*3+2)/(2+2) 。
1、实现思路
a、建立OPTR（运算符）和OPND（数字）两个栈，后输入字符串以'='结束
b、自左向右扫描表达式
若读取到数字，直接压入操作数栈，继续处理下一个字符；
若读取到运算符，比较栈顶算符与读取的算符的优先级：
栈顶算符 < 读取的算符
将读取的算符压入栈，继续处理下一个字符；
栈顶算符 > 读取的算符
栈顶算符出栈，从操作数栈中取出两数字， 根据出栈算符做运算，运算结果再压入操作数栈，继续处理当前字符；
栈顶算符 == 读取的算符
栈顶算符出栈，括号出栈不保存，继续处理下一个字符；
c、 结束条件是算符栈已空，最后操作数栈出栈输出计算结果。
2、运算符关系表
例如：
3*(7-2)
3、代码实现
3.1、定义全局数组存放合法的运算符
static char opts[] = {'+','-','*','/','(',')','\n'};3.2、实现函数判断当前字符是不是运算符
// 定义函数，判断当前的字符是不是运算符,如果是返回在运算符数组中的下标，如果不是返回-1
int isOpt(const char ch)
{ int len = sizeof(opts) / sizeof(char);int i;for(i=0;i<len;i++){if(opts[i] == ch){return i;}}return -1;
} 3.3、实现函数判断栈顶运算符和当前输入运算符的关系
// 定义函数获取栈顶运算符和当前输入运算符之间的关系
char Precede(SElemType ch1,SElemType ch2)
{// 根据运算符优先级表格，使用二维数组存储字符之间的关系 static char optsRelationArr[7][7] = {{'>','>','<','<','<','>','>'},{'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},{'<','<','<','<','<','=',-1}, {'>','>','>','>',-1,'>','>'}, {'<','<','<','<','<',-1,'='}};// 获取两个字符的排序下标 int idx1 = isOpt(ch1);int idx2 = isOpt(ch2);// 字符不存在直接返回-1 if(idx1 < 0 || idx2 < 0) return -1; // 合法返回对应关系return optsRelationArr[idx1][idx2];
}3.4、实现函数根据运算符求+-*/结果
// 定义函数进行算数运算
SElemType Operator(SElemType a,SElemType x,SElemType b)
{switch(x){case '+':return a + b;case '-':return a - b;case '*':return a * b;case '/':return a / b; }
}3.5、实现函数求表达式的结果
SElemType EvalueExpression()
{// 定义操作数栈和运算符栈SqStack OPND,OPTR;// 定义变量存储 计算中的两个数据SElemType a,b;// 定义变量存储数据出现多位数据的运算中间量 12 45这类操作数SElemType d;// 定义变量存储 运算栈栈顶字符SElemType x;// 定义变量存储用户输入的字符符号char c;// 初始化操作数栈和运算符栈InitStack(&OPND);InitStack(&OPTR);// 现象运算符栈中添加\n作为运算结束Push(&OPTR,'\n');x = '\n';// 接收一个字符c = getchar();// 循环结束数据并运算 // 结束条件为 ,循环条件为相反面： !(c=='\n' && x=='\n') while(!(c=='\n' && x=='\n')) {if(isOpt(c) >= 0){// c为运算符 ，比较x和c的大小char res = Precede(x,c);switch(res) {case '<':// 当前运算符入栈Push(&OPTR,c); // 继续接收下一个字符输入c = getchar();// 结束匹配break;case '=':// 移除运算符栈顶的运算符 () 和 \n和\n相遇Pop(OPTR,&x);// 继续接收下一个字符输入c = getchar();// 结束匹配break;case '>':// 移除运算符栈顶的运算符Pop(OPTR,&x);// 移除操作数栈栈顶两个数据Pop(OPND,&b);Pop(OPND,&a);// 计算后结果入栈Push(&OPND,Operator(a,x,b));// 结束匹配 break;}}else if(c >= '0' && c <= '9'){d = 0;// c为数字字符 -- 注意处理多个数字字符组合成一个数字的情况while(c >= '0' && c <= '9'){d = d * 10 + c - '0';c = getchar();}// 接收完毕将数据入栈 Push(&OPND,d); } else if(c == '\b'){// c为退格符 -- 有待完善 }else{// 非法字符printf("出现非法字符\n");exit(OVERFLOW); } // 获取运算符栈顶数据，继续下一轮的运算 GetTop(OPTR,x);}/***** 运算结束 *******/ // 移除操作数栈 栈顶元素Pop(OPND,&x);// 如果操作栈为空则结果为栈顶元素，否则表达式不正确if(!StackEmpty(OPND)){printf("表达式有问题\n");exit(OVERFLOW);} return x;
} 3.6、main函数测试结果
int main(int argc, char *argv[]) {printf("请输入算数表达式，负数用(0-正数)表示："); SElemType res = EvalueExpression();printf("%d",res); return 0;
}
