【C++】スタックを使って後置記法（逆ポーランド記法）の式を評価する方法

後置記法とは

後置記法（ポストフィックス記法）は「逆ポーランド記法（Reverse Polish Notation）」とも呼ばれる数式の表記方法で、演算子をオペランドの後に配置するのが特徴です。この記法で書かれた式を評価するには、スタックというデータ構造を利用するのが一般的です。

例えば、式が「21+3*」であれば、計算結果は 9 になります。これは通常の中置記法でいう「(2 + 1) × 3 = 9」に相当します。

評価アルゴリズムの手順

スタックを使って後置記法の式を評価する際の基本的な流れは以下の通りです。

• 後置記法の式に含まれる各文字 ch について、次の処理を行います。
  • ch が演算子 ⊙ の場合：
    • a := スタックから最初の要素をポップする
    • b := スタックから次の要素をポップする
    • res := b ⊙ a を計算する
    • res をスタックにプッシュする
  • ch がオペランドの場合：
    • ch をスタックにプッシュする
• 最後に、スタックのトップにある要素を返します。これが式全体の評価結果となります。

C++による実装例

それでは、実際のC++コードを見ていきましょう。

サンプルコード

#include<bits/stdc++.h>
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 = "21+3*";
   cout <<postfixEval(post);
}

入力

"21+3*"

出力

9

コードの解説

このプログラムを構成する各関数の役割は以下の通りです。

• scanNum()： 文字を対応する数値（float型）に変換します。
• isOperator()： 文字が演算子（+, -, *, /, ^）かどうかを判定します。
• isOperand()： 文字が数字（オペランド）かどうかを判定します。
• operation()： 指定された演算子に基づいて実際の四則演算やべき乗を行います。
• postfixEval()： 評価処理の中心となる関数です。式を左から右へ走査し、オペランドであればスタックにプッシュし、演算子であればスタックから2つの値をポップして計算した結果を再びプッシュします。

実装上の注意点として、演算の順序が挙げられます。先にポップした値 a が右側のオペランド、後からポップした値 b が左側のオペランドとなるため、減算や除算では「b − a」「b ÷ a」のように計算する必要があります。この順序を間違えると、正しい結果が得られなくなります。