將中綴表示式轉換為字尾表示式

中綴表示式可讀，人類可以解決。我們可以輕鬆區分運算子的順序，並且還可以在解決數學表示式時使用括號首先解決該部分。計算機無法輕鬆區分運算子和括號，因此需要字尾轉換。

要將中綴表示式轉換為字尾表示式，我們將使用 棧資料結構。從左到右掃描中綴表示式，當我們獲得任何運算數時，只需將它們新增到字尾形式中，而對於運算子和括號，將它們新增到棧中，同時維護它們的優先順序。

注意：此處我們只考慮 {+, −, ∗, /, ^} 運算子，忽略其他運算子。

輸入和輸出

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+

Arjun Thakur

更新日期： 02-Sep-2023

71K+ 瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始