求解后缀表达式


为了求解数学表达式,我们需要前缀或后缀形式。将中缀转换为后缀后,我们需要后缀求值算法以找到正确答案。

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

从后缀表达式中,找到一些运算数时,将它们压入堆栈。找到一些运算符时,从堆栈中弹出两个项并按正确顺序执行运算。之后,结果也会压入堆栈以供将来使用。完成整个表达式后,最终结果也会存储在堆栈顶。

输入和输出

Input:
Postfix expression: 53+62/*35*+
Output:
The result is: 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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

#include<iostream>
#include<cmath>
#include<stack>
using namespace std;

float scanNum(char ch) {
   int value;
   value = ch;
   return float(value-'0');   //return float from character
}

int isOperator(char ch) {
   if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
      return 1;    //character is an operator
   return -1;   //not an operator
}

int isOperand(char ch) {
   if(ch >= '0' && ch <= '9')
      return 1;    //character is an operand
   return -1;   //not an operand
}

float operation(int a, int b, char op) {
   //Perform operation
   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);    //find b^a
   else
      return INT_MIN;    //return negative infinity
}

float postfixEval(string postfix) {
   int a, b;
   stack<float> stk;
   string::iterator it;

   for(it=postfix.begin(); it!=postfix.end(); it++) {
      //read elements and perform postfix evaluation
      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 << "The result is: "<<postfixEval(post);
}

输出

The result is: 39

更新于: 17-6-2020

8 千 + 阅览

开启你的 职业生涯

完成课程以获取认证

开始
广告