中置を後置式に変換する

中置式は、人間が読み取りおよび解決できます。演算子の順序は簡単に区別できます。また、数式を解くときに括弧を使用してその部分を最初に解くことができます。コンピューターは演算子と括弧を簡単に区別できないため、接尾辞の変換が必要です。

中置式を後置式に変換するには、スタックデータ構造を使用します。中置式を左から右にスキャンすることにより、オペランドを取得するときに、それらを接尾辞フォームに追加し、演算子と括弧については、それらの優先順位を維持しながらスタックに追加します。

注： ここでは、{+、−、∗、/、^}演算子のみを検討し、他の演算子は無視します。

入力と出力

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+