중위를 후위 표현식으로 변환

중위 표현은 사람이 읽고 풀 수 있습니다. 연산자의 순서를 쉽게 구분할 수 있으며 수학식을 풀 때 괄호를 사용하여 해당 부분을 먼저 풀 수 있습니다. 컴퓨터는 연산자와 괄호를 쉽게 구별하지 못하므로 후위 변환이 필요합니다.

중위 표현식을 후위 표현식으로 변환하기 위해 스택 데이터 구조를 사용합니다. 중위 표현식을 왼쪽에서 오른쪽으로 스캔하여 피연산자를 얻으면 단순히 후위 형식에 추가하고 연산자와 괄호에 대해서는 우선 순위를 유지하면서 스택에 추가합니다.

참고: 여기서는 {+, −,*,/, ^} 연산자만 고려하고 다른 연산자는 무시합니다.

입력 및 출력

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+