Question

数据结构栈的表达式求值应用，改代码

// evaluateExpreesion.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "adtstack.h"
int In(char c)
{
switch (c)
{
case '+':
case '-':
case '/':
case '*':
case '(':
case ')': return 1;
default: return 0;
break;
}
}
char Precede(char a, char c)
{//判断栈顶a和新运算符c的大小关系，>表示a大于c的运算优先级
if (a == '+' || a == '-')
{//a=加或减

if (c == '*' || c == '/' || c == '（')
return '<';
return '>';
}
if (a == '*' || a == '/')
{//a=乘或除
if (c == '(')
return '<';//小于号
return '>';//大于号
}
if (a == '(')//a=左括号
{
if (c == ')')
return '=';
return '<';
}
if (a == ')') {
//a=右括号
return '>';
}
if (c == '#') return '>';

}//Precede
int transform(char a)
{//将数字字符转换为整型数据
return a - 48;

}
int operate(int a, char theta, int b)
{
switch (theta)
{
case '+': return a+b; break;
case '-': return a-b; break;
case '*': return a*b; break;
case '/': return a/b; break;
default: return ERROR;
break;
}
}
int evaluateExpression()
{
printf("请输入表达式，以#结束：");
IntStack OPND;// OPND为操作数栈
SqStack OPTR;//创建OPTR运算符栈
char theta,e,c;//创建x，theta字符型变量
int a, b;//创建int型变量a，b
InitStack(OPTR); Push(OPTR, '#');//创建字符栈并将‘#’放入栈底
InitIntStack(OPND); //创建整型栈
while ((c=getchar()) != '#' )//当接受到的字符c不是#或运算符栈顶不是#时
{
if (!In(c)) {
PushInt(OPND, transform(c)); c = getchar(); printf("%d", GetTopInt(OPND, a));
}//如果c不是运算符，则将c转换为整型后放入整形栈的栈底，并再次输入字符
else//如果c是运算符
{

switch (Precede(GetTop(OPTR,e),c))//通过Precede函数将运算符栈顶的运算符e与c比较，e比c运算级高则返回'>',反之返回'<",相等返回'='
{
case '<': //新运算符的运算级比里面的大
Push(OPTR, c); c = getchar();//将c放入运算符栈

break;
case '='://e的运算级与c相等
Pop(OPTR, e); c = getchar();//脱括号并接受下一字符
break;
case '>'://里面的运算符大 退栈并将运算结果入整型栈
Pop(OPTR, theta);
PopInt(OPND, a); PopInt(OPND, b);
PushInt(OPND, operate(a, theta, b));
printf("%d", operate(a, theta, b));
break;
}//switch
}
return GetTopInt(OPND, a);
}//while
while (!StackIntEmpty(OPND))
{
Pop(OPTR, theta);
PopInt(OPND, a); PopInt(OPND, b);
PushInt(OPND, operate(a, theta, b));
}
return GetTopInt(OPND, a);
}//evaluateExpression
int main()
{
printf("%d",evaluateExpression());
return 0;
}
这样运行的程序是错误的。栈的头文件由于篇幅放不上来。烦请大神帮忙看看哪里出错

Answer 1

表达式求值是栈的一个重要的应用。例如计算器中的加减乘除表达式的计算，都会使用栈来进行求值。 
表达式的表示方法主要有中缀表示法和后缀表示法。

• 中缀表示法：操作符号处于两个操作数的中间例如3+4，中缀表达式是符合人们思维的算术表达式方法，中缀表达式通常包含圆括号和方括号。中缀表达式不容易被计算机所理解，因此不太方便使用其进行表达式求值。