逆ポーランド記法の数式を計算する

データ構造

こんにちは。

前回まででスタック・キュー・2分木を作ったので、これらを使ってみようと思います。

そこで、簡易な電卓を作ってみます。

前置記法・中置記法・後置記法

普段使っている数式は、演算子が数と数の間に置かれている中置記法というものです。

他に演算子を前に置く前置記法、演算子を後ろに置く後置記法があります。

前置記法をポーランド記法、後置記法を逆ポーランド記法ともいいます。

例えば中置記法の 1+2 は、前置記法では + 1 2 、後置記法では 1 2 + と表記します。

中置記法の（１+２）＊（3+４）を前置記法と後置記法では、次のようになります。

前置記法　：　* + 1 2 + 3 4

後置記法　：　1 2 + 3 4 + *

となります。前置記法と後置記法では括弧がなくても数式を表現できるのですが、中置記法では括弧が必要です。

上の中置記法の数式を括弧なしで表現すると　1 + 2 * 3 + 4 となり、別の数式になってしまいます。

逆ポーランド記法を計算する

これらの記法のうち、逆ポーランド記法は前から順に読み込んで数式を処理することができます。

逆ポーランド記法を計算するにはスタックを使います。

数値を読み込んだらスタックに値を積み、演算子を読み込んだらスタックから２つの値を取り出して計算して計算結果をスタックに積みます。

最後にスタックに残った値が計算結果になります。

1 2 + 3 4 + * を例にして計算してみます。

入力 1 :スタックに積む [1]
入力 2 : スタックに積む [2←1]
入力 + : スタックから2つの値を取り出して計算する 1 + 2 = 3 これをスタックに積む [3]
入力 3 : スタックに積む [3←3]
入力 4 : スタックに積む [4←3←3]
入力 + : スタックから2つの値を取り出して計算する。 3 + 4 = 7 これをスタックに積む[7←3]
入力 * : スタックから2つの値を取り出して計算する。 3 * 7 = 21 これをスタックに積む[21]

入力をすべて用いた後にスタックから値を１つ取り出したものが計算結果になります。

C++でプログラムを書いてみる

上の計算をC++でプログラムを書いてみます。

最後にスタックに余計な値がある場合には、数式を受理しないでエラーを返すことにしています。

ファイル名は MyReversePolishNotation.h とします。

#pragma once
#include"MyStack.h"
#include<iostream>
using namespace std;

class MyReversePolishNotation
{
public:
    MyReversePolishNotation(){
        this->_st = new MyStack<double>();
    }

    int calc(string s){
        string tmp = "";
        double result;
        for (int i = 0; i < s.size();i++){
            if(s[i]==' '){
                if(tmp!=""){
                    this->_st->push(stod(tmp));
                }
                tmp = "";
                continue;
            }

            if(isdigit(s[i])){
                tmp += s[i];
                continue;
            }

            tmp += s[i];
            if(_st->empty()){
                throw runtime_error("Formula error");
            }
            double v2 = _st->pop();
            if(_st->empty()){
                throw runtime_error("Formula error");
            }
            double v1 = _st->pop();
            if(tmp=="+"){
                result = v1 + v2;
            } else if(tmp=="-"){
                result = v1 - v2;
            } else if(tmp=="*"){
                result = v1 * v2;
            } else if(tmp=="/"){
                result = v1 / v2;
            } else {
                throw runtime_error("Formula error");
            }
            this->_st->push(result);
            tmp = "";
        }

        result = _st->pop();
        if(!_st->empty() || tmp!=""){
            throw runtime_error("Formula error");
        }
        return result;
    }

private:
    MyStack<double>* _st;
};

このプログラムを呼び出してみます。

#include<iostream>
#include<string>
#include"MyReversePolishNotation.h"
using namespace std;

int main(){
    MyReversePolishNotation rpn;
    cout << rpn.calc("10 9 +") << endl;
    cout << rpn.calc("8 7 -") << endl;
    cout << rpn.calc("6 5 *") << endl;
    cout << rpn.calc("4 3 /") << endl;

    cout << rpn.calc("1 2 + 3 4 + *") << endl;

    cout << rpn.calc("2 3 + 4 5 +") << endl;
}

実行結果です。

19
1
30
1.33333
21
terminate called after throwing an instance of 'std::runtime_error'
  what():  Formula error

最後のエラーは数式を受理しなかった結果によるものです。

今回はこれでおしまいにします。それではまた。

Posted by 春日井 優