使用堆栈计算表达式的 C++ 程序

为了求解数学表达式，我们需要前缀或后缀形式。将中缀转换为后缀后，我们需要后缀评估算法来找到正确的答案。

这里我们也必须使用堆栈数据结构来解决后缀表达式。

从后缀表达式中，当找到一些操作数时，将它们压入堆栈。当找到某个运算符时，从堆栈中弹出两个项目，然后按正确的顺序执行操作。之后，结果也被压入堆栈以备将来使用。完成整个表达式后，最终结果也存入栈顶。

Input: Postfix expression: 53+62/*35*+
Output: 结果是： 39

算法

postfixEvaluation(postfix)

输入：要计算的后缀表达式。

输出：评估后缀形式后的答案。

Begin
   for each character ch in the postfix expression, do
      if ch is an operator , then
         a := pop first element from stack
         b := pop second element from the stack
         res := b a
         push res into the stack
      else if ch is an operand, then
         add ch into the stack
   done
   return element of stack top
End

示例代码

#include<iostream>
#include<cmath>
#include<stack>
using namespace std;
float scanNum(char ch) {
   int value;
   value = ch;
   return float(value-'0');   //从字符返回浮点数
}
int isOperator(char ch) {
   if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
      return 1;    //字符是一个运算符
   return -1;   //不是运营商
}
int isOperand(char ch) {
   if(ch >= '0' && ch <= '9')
      return 1;   //字符是一个操作数
   return -1;   //不是操作数
}
float operation(int a, int b, char op) {
   //执行操作
   if(op == '+')
      return b+a;
   else if(op == '-')
      return b-a;
   else if(op == '*')
      return b*a;
   else if(op == '/')
      return b/a;
   else if(op == '^')
      return pow(b,a); //找到 b^a
   else
      return INT_MIN; //返回负无穷大
}
float postfixEval(string postfix) {
   int a, b;
   stack<float> stk;
   string::iterator it;
   for(it=postfix.begin(); it!=postfix.end(); it++) {
      //读取元素并执行后缀评估
      if(isOperator(*it) != -1) {
         a = stk.top();
         stk.pop();
         b = stk.top();
         stk.pop();
         stk.push(operation(a, b, *it));
      }else if(isOperand(*it) > 0) {
         stk.push(scanNum(*it));
      }
   }
   return stk.top();
}
main() {
   string post = "53+62/*35*+";
   cout << "结果是： "<<postfixEval(post);
}

结果是： 39