Chuyển đổi Infix thành Postfix Expression

Con người có thể đọc và giải được các biểu thức infix. Chúng ta có thể dễ dàng phân biệt thứ tự của các toán tử và cũng có thể sử dụng dấu ngoặc để giải phần đó trước khi giải các biểu thức toán học. Máy tính không thể dễ dàng phân biệt các toán tử và dấu ngoặc đơn, đó là lý do tại sao cần chuyển đổi hậu tố.

Để chuyển đổi biểu thức infix thành biểu thức hậu tố, chúng ta sẽ sử dụng cấu trúc dữ liệu ngăn xếp. Bằng cách quét biểu thức infix từ trái sang phải, khi chúng ta nhận được bất kỳ toán hạng nào, chỉ cần thêm chúng vào biểu mẫu hậu tố và đối với toán tử và dấu ngoặc đơn, hãy thêm chúng vào ngăn xếp để duy trì mức độ ưu tiên của chúng.

Lưu ý: Ở đây chúng tôi sẽ chỉ xem xét các toán tử {+, -, ∗, /, ^}, các toán tử khác bị bỏ qua.

Đầu vào và Đầu ra

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

Thuật toán

infixToPostfix(infix)

Đầu vào - Biểu thức infix.

Đầu ra - Chuyển đổi biểu thức infix thành dạng postfix.

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

Ví dụ

#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;
}

Đầu ra

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