本章内容使用上述栈结构函数，来完成表达式求值操作。
表达式例如：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);
// 继续接收下一个字符输入
//scanf(" %c",&c);
c = getchar();
// 结束匹配
break;
case '=':
// 移除运算符栈顶的运算符 () 和 \n和\n相遇
Pop(&OPTR,&x);
// 继续接收下一个字符输入
//scanf(" %c",&c);
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';
// scanf(" %c",&c);
c = getchar();
}
// 接收完毕将数据入栈
Push(&OPND,d);
}
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;
}
