将中缀表达式转换为后缀表达式

中缀表达式可读且可被人理解。我们可以轻松区分运算符的顺序，也可以使用括号在解决数学表达式时首先解决部分内容。计算机不能轻松地区分运算符和括号，因此需要后缀转换。

要将中缀表达式转换为后缀表达式，我们将使用栈数据结构。从左向右扫描中缀表达式，当得到任何运算符时，简单地将它们添加到后缀形式中，对于运算符和括号，将它们添加到栈中，保持它们的优先级。

注意：这里我们仅考虑 {+, −, ∗, /, ^} 运算符，其他运算符将被忽略。

输入和输出

Input:
The infix expression. x^y/(5*z)+2
Output:
Postfix Form Is: xy^5z*/2+

算法

infixToPostfix(infix)

输入 − 中缀表达式。

输出 − 将中缀表达式转换为后缀形式。

Begin
   initially push some special character say # into the stack
   for each character ch from infix expression, do
      if ch is alphanumeric character, then
         add ch to postfix expression
      else if ch = opening parenthesis (, then
         push ( into stack
      else if ch = ^, then            //exponential operator of higher precedence
         push ^ into the stack
      else if ch = closing parenthesis ), then
         while stack is not empty and stack top ≠ (,
            do pop and add item from stack to postfix expression
         done

         pop ( also from the stack
      else
         while stack is not empty AND precedence of ch <= precedence of stack top element, do
            pop and add into postfix expression
         done

         push the newly coming character.
   done

   while the stack contains some remaining characters, do
      pop and add to the postfix expression
   done
   return postfix
End

示例

#include<iostream>
#include<stack>
#include<locale>      //for function isalnum()
using namespace std;

int preced(char ch) {
   if(ch == '+' || ch == '-') {
      return 1;              //Precedence of + or - is 1
   }else if(ch == '*' || ch == '/') {
      return 2;            //Precedence of * or / is 2
   }else if(ch == '^') {
      return 3;            //Precedence of ^ is 3
   }else {
      return 0;
   }
}

string inToPost(string infix ) {
   stack<char> stk;
   stk.push('#');               //add some extra character to avoid underflow
   string postfix = "";         //initially the postfix string is empty
   string::iterator it;

   for(it = infix.begin(); it!=infix.end(); it++) {
      if(isalnum(char(*it)))
         postfix += *it;      //add to postfix when character is letter or number
      else if(*it == '(')
         stk.push('(');
      else if(*it == '^')
         stk.push('^');
      else if(*it == ')') {
         while(stk.top() != '#' && stk.top() != '(') {
            postfix += stk.top(); //store and pop until ( has found
            stk.pop();
         }
         stk.pop();          //remove the '(' from stack
      }else {
         if(preced(*it) > preced(stk.top()))
            stk.push(*it); //push if precedence is high
         else {
            while(stk.top() != '#' && preced(*it) <= preced(stk.top())) {
               postfix += stk.top();        //store and pop until higher precedence is found
               stk.pop();
            }
            stk.push(*it);
         }
      }
   }

   while(stk.top() != '#') {
      postfix += stk.top();        //store and pop until stack is not empty.
      stk.pop();
   }

   return postfix;
}

int main() {
   string infix = "x^y/(5*z)+2";
   cout << "Postfix Form Is: " << inToPost(infix) << endl;
}

输出

Postfix Form Is: xy^5z*/2+

更新时间： 2023 年 9 月 2 日

7.1 万加的浏览次数

开启你的 职业 生涯

完成课程，获得认证

开始
广告