後置式（ポストフィックス記法）の評価方法｜スタックを使ったアルゴリズムとC++実装例

数式をコンピュータで計算する際には、前置記法（プレフィックス）や後置記法（ポストフィックス）の形式が用いられます。中置記法（インフィックス）から後置記法へ変換した後、正しい答えを得るためには「後置式の評価アルゴリズム」が必要になります。

後置式の評価においても、スタックというデータ構造を利用します。

後置式評価の基本手順

後置式を左から右へ読み進めながら、次のルールに従って処理を行います。

• オペランド（数値）を見つけた場合：スタックにプッシュする
• 演算子を見つけた場合：スタックから2つの値をポップし、正しい順序で演算を実行する
• 演算結果は、その後の計算に備えて再びスタックにプッシュする
• 式全体の読み取りが完了すると、スタックのトップに最終結果が格納される

入力と出力

入力：
後置式：53+62/*35*+
出力：
計算結果：39

アルゴリズム

postfixEvaluation(postfix)

入力：評価対象となる後置式

出力：後置式を評価した結果の値

Begin
   for each character ch in the postfix expression, do
      if ch is an operator ⨀ , then
         a := pop first element from stack
         b := pop second element from the stack
         res := b ⨀ a
         push res into the stack
      else if ch is an operand, then
         add ch into the stack
   done
   return element of stack top
End

動作の流れ（53+62/*35*+ の場合）

例として「53+62/*35*+」を評価する過程を順番に見てみましょう。

C++による実装例

#include<iostream>
#include<cmath>
#include<stack>
using namespace std;

float scanNum(char ch) {
   int value;
   value = ch;
   return float(value-'0');  // 文字を数値(float)に変換して返す
}

int isOperator(char ch) {
   if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
      return 1;     // 演算子である場合
   return -1;  // 演算子ではない場合
}

int isOperand(char ch) {
   if(ch >= '0' && ch <= '9')
      return 1;     // オペランドである場合
   return -1;  // オペランドではない場合
}

float operation(int a, int b, char op) {
   // 演算を実行する
   if(op == '+')
      return b+a;
   else if(op == '-')
      return b-a;
   else if(op == '*')
      return b*a;
   else if(op == '/')
      return b/a;
   else if(op == '^')
      return pow(b,a);     // b^a（べき乗）を計算
   else
      return INT_MIN;     // 異常値として負の最小値を返す
}

float postfixEval(string postfix) {
   int a, b;
   stack<float> stk;
   string::iterator it;

   for(it=postfix.begin(); it!=postfix.end(); it++) {
      // 要素を読み込みながら後置式を評価する
      if(isOperator(*it) != -1) {
         a = stk.top();
         stk.pop();
         b = stk.top();
         stk.pop();
         stk.push(operation(a, b, *it));
      }else if(isOperand(*it) > 0) {
         stk.push(scanNum(*it));
      }
   }
   return stk.top();
}

main() {
   string post = "53+62/*35*+";
   cout << "The result is: "<<postfixEval(post);
}

実行結果

The result is: 39

このように、スタックを利用することで後置式を効率的に評価できます。演算子が出現した際のポップの順序――先にポップした値を右オペランド、次にポップした値を左オペランドとして扱う――を間違えないことが、正しく計算するための重要なポイントです。