如何使用堆栈c评估算术表达式？

到现在为止，我刚刚完成表达式转向后缀表达式，我尝试评估，但出现了问题并让我困惑很长时间，我只知道如何解决它。

这是我的代码转向后缀表达式：

#include  #include  #include  #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 #define MAXBUFFER 10 #define OK 1 #define ERROR 0 typedef char ElemType; typedef int Status; typedef struct { ElemType *base; ElemType *top; int stackSize; }sqStack; Status InitStack(sqStack *s) { s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if ( !s->base ) { exit(0); } s->top = s->base; s->stackSize = STACK_INIT_SIZE; return OK; } Status Push(sqStack *s, ElemType e) { //if the stack is full if ( s->top - s->base >= s->stackSize ) { s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType)); if ( !s->base ) { exit(0); } s->top = s->base + s->stackSize; s->stackSize += STACKINCREMENT; } //store data *(s->top) = e; s->top++; return OK; } Status Pop(sqStack *s, ElemType *e) { if ( s->top == s->base ) { return ERROR; } *e = *--(s->top); return OK; } int StackLen(sqStack s) { return (s.top - s.base); } int main() { sqStack s; char c; char e; InitStack(&s); printf("Please input your calculate expression(# to quit):\n"); scanf("%c", &c); while ( c != '#' ) { while ( c >= '0' && c <= '9' ) { printf("%c", c); scanf("%c", &c); if ( c  '9' ) { printf(" "); } } if ( ')' == c ) { Pop(&s, &e); while ( '(' != e ) { printf("%c ", e); Pop(&s, &e); } } else if ( '+' == c || '-' == c ) { if ( !StackLen(s) ) { Push(&s, c); } else { do { Pop(&s, &e); if ( '(' == e ) { Push(&s, e); } else { printf("%c", e); } }while ( StackLen(s) && '(' != e ); Push(&s, c); } } else if ( '*' == c || '/' == c || '(' == c ) { Push(&s, c); } else if ( '#' == c ) { break; } else { printf("\nInput format error!\n"); return -1; } scanf("%c", &c); } while ( StackLen(s) ) { Pop(&s, &e); printf("%c ", e); } return 0; } 

当我把3 *（7-2​​）＃它返回3 7 2 –

事情是正确的，但我不知道如何评估它接下来，我只是把它变成postfix表达式，我想用堆栈来评估它。

Answer 1

在转换为波兰表示法时，您根本没有处理运算符优先级。 很难给出完整的代码，但这就是我假设我们沿着strBuild构建一个字符串的strBuild 。

转换为RPN

  if (token is integer) { strBuild.Append(token); strBuild.Append(" "); } else if (token is Operator) { while (isOperator(Stack.Peek())) { if (GetExprPrecedence(token) <= GetExprPrecedence(Stack.Peek())) { strBuild.Append(Stack.Pop()); strBuild.Append(" "); } else break; } Stack.Push(token); } else if (token == '(') { Stack.Push(token); } else if (token == ')') { while (Stack.Peek() != '(') { if (Stack.Count > 0) { strBuild.Append(Stack.Pop()); strBuild.Append(" "); } else { Show("Syntax Error while Parsing"); break; } } Stack.Pop(); } while (Stack.Count > 0 && isOperator(Stack.Peek())) { if (Stack.Peek() == '(' || Stack.Peek() == ')') { MessageBox.Show("All Tokens Read - Syntax Error"); break; } Stack.Pop(); } return strBuild; 

strBuild应该是RPN字符串。 现在评估。

评估

  for (int i = 0; i < StrPostFix.Length; i++) { token = StrPostFix[i]; if (isOperator(token)) { switch (token) { case "/": op2 = Stack.Pop(); op1 = Stack.Pop(); val = op1 / op2; break; case "*": op2 = Stack.Pop(); op1 = Stack.Pop(); val = op1 * op2; break; case "+": op2 = Stack.Pop(); op1 = Stack.Pop(); val = op1 + op2; break; case "-": op2 = Stack.Pop(); op1 = Stack.Pop(); val = op1 - op2; break; } Stack.Push(val); } else Stack.Push(token); } return Stack.Pop(); 

return Stack.Pop(); 弹出评估值并返回。 现在，对于你没有回答的主要问题我没有回答，这就是你如何处理优先问题：

 enum OperatorPrecedence { Add, Minus, Mult, Div, Brackets }; int GetExprPrecedence(string op) { int p = 0; switch (op) { case "(": p = (int)OperatorPrecedence .Brackets; break; case "/": p = (int)OperatorPrecedence .Div; break; case "*": p = (int)OperatorPrecedence .Mult; break; case "-": p = (int)OperatorPrecedence .Minus; break; case "+": p = (int)OperatorPrecedence .Add; break; } return p; } 

请注意，伪代码类似于C-Sharp，因为这是我的工作。 我尽力让它看起来像算法，也不是模糊的，这样你就可以与你的代码相关联。 我的算法结果：

注意我使用Box Brackets [而不是Round (对于我的表达式。最终答案是15。