数回に分けて、四則演算を行う数式（例えば、(1＋5) * (2+3)のような式）を入力し、その計算結果を求めるプログラムを書いて行こうと思います。
第一回目の今回は、逆ポーランド記法で表された数式を計算するクラスを定義します。
逆ポーランド記法を利用した数式の計算(1) 逆ポーランド記法の計算 ← 当記事
逆ポーランド記法を利用した数式の計算(2) 数式をトークンに分割する
逆ポーランド記法を利用した数式の計算(3) ReversePolishNotationクラスを改良する
逆ポーランド記法を利用した数式の計算(4) Contextクラスを定義する
逆ポーランド記法を利用した数式の計算(5) Interpreterパターンで数式を解析する
逆ポーランド記法を利用した数式の計算(6) 最後の仕上げ
逆ポーランド記法とは
逆ポーランド記法（Reverse Polish Notation, RPN）とは、数式の記述方法で、演算子を被演算子の後に記述する表記法です。日本語では、後置記法とも呼ばれたりします。
この記法は、演算の優先順位を指定する括弧が不要な点が特徴のひとつです。
たとえば、(1＋5) * (2+3)は、
1 5 + 2 3 + *
と記述します。
詳しくは、Wikipediaのページをご覧ください。
逆ポーランド記法で表記された数式を計算する
まずは、逆ポーランド記法を表すクラスReversePolishNotationを定義します。
ReversePolishNotationクラス
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Rpn.App {
public class ReversePolishNotation {
public IEnumerable<string> Tokens { get; }
public ReversePolishNotation(IEnumerable<string> tokens) {
Tokens = tokens.ToList();
}
public ReversePolishNotation(string exp) {
var tokens = exp.Split(' ').Where(s => s != "");
Tokens = tokens.ToList();
}
}
}
このクラスは、与えられた式(文字列形式)を空白で区切って、リストに保持しているだけの簡単なものです。
2つのコンストラクタとプロパティを持っています。
RpnCalculatorクラス
次に、このReversePolishNotationクラスが保持している式を計算するクラスRpnCalculatorを定義します。
Wikipediaに書かれているように、スタック(Stack<T>)クラスを利用し、計算をしています。
ReversePolishNotationクラスに保持されたリストの先頭から順に要素を取り出し、演算子でなければ(つまり数値ならば）、スタックにその値を積み、演算子だったら、スタックから値を２つ取り出し計算を行い、その結果をスタックに積みます。これを繰り返すことで、計算を行います。
例えば、1 5 + 2 3 + *ならば、
- リストから 1 を取り出し、スタックに積む
- リストから 5 を取り出し、スタックに積む
- リストから + を取り出す。演算子なので、スタックから値を2つ取り出し、1 + 5 を計算する。その結果の6をスタックに積む
- リストから 2 を取り出し、スタックに積む
- リストから 3 を取り出し、スタックに積む
- リストから + を取り出し、演算子なので、スタックから値を2つ取り出し、2 + 3 を計算する。その結果の5をスタックに積む
- リストから * を取り出す。演算子なので、スタックから値を2つ取り出し、5 * 6 を計算する。その結果の30をスタックに積む
- リストが空になったので、スタックから値(30)を取り出す。これが最終的な結果となる。
とこんな感じで、計算をしていきます。
スタックの状態は、以下のように変化します。左側がスタックのTOPです。
- [1]
- [5, 1]
- [6]
- [2, 6]
- [3, 2, 6]
- [5, 6]
- [30]
- []
これをコードにしたのが、以下のRpnCalculatorクラスです。
using System;
using System.Net;
using System.Collections.Generic;
namespace Rpn.App {
public class RpnCalculator {
// 後置記法を計算する
public static decimal Calculate(ReversePolishNotation rpn) {
Stack<object> stack = new Stack<object>();
foreach (var token in rpn.Tokens) {
if (IsOperator(token)) {
var b = (decimal)stack.Pop();
var a = (decimal)stack.Pop();
var c = Operate(a, b, token);
stack.Push(c);
} else {
stack.Push(decimal.Parse(token));
}
}
return (decimal)stack.Pop();
}
private static decimal Operate(decimal a, decimal b, string ope) {
switch (ope) {
case "+":
return a + b;
case "-":
return a - b;
case "*":
return a * b;
default:
return a / b;
}
}
public static bool IsOperator(string s) {
if (s.Length == 1) {
if (s[0] == '+' || s[0] == '-' || s[0] == '*' || s[0] == '/')
return true;
}
return false;
}
}
}
このクラスは、staticクラスとしました。
すべての計算が終わった時には、スタックの先頭に計算結果が入っているので、それを返すようにしています。
Mainメソッド
ここまでできれば、コンソールから逆ポーランド記法の数式を入力し、それを計算するコードは簡単に書けますね。
using System;
using System.Linq;
namespace Rpn.App {
class Program {
static void Main(string[] args) {
while (true) {
try {
var exp = Console.ReadLine();
if (exp == null)
break;
var rpn = new ReversePolishNotation(exp);
var s = rpn.Tokens.Aggregate((t, v) => $"{t} {v}");
var ans = RpnCalculator.Calculate(rpn);
Console.WriteLine($"{s} = {ans}");
} catch (Exception ex) {
Console.WriteLine(ex.ToString());
}
}
}
}
}
Ctrl+Z<Enter>するまで、繰り返しています。
実行例
以下、実行例です。
5 9 +
5 9 + = 14
18 5 -
18 5 - = 13
4 2 + 5 3 + *
4 2 + 5 3 + * = 48
^Z
続行するには何かキーを押してください . . .
無事、実行できました。
ということで、RpnCalculator.Calculateができたので、あとは、通常の数式を逆ポーランド記法に変換することができれば、キーボードから入力された数式を計算するプログラムが書けるということですね。
ただ、数式を逆ポーランド記法に変換するのが、意外と厄介なんですよね。
次回からは、数式を逆ポーランド記法に変換して、それを計算するプログラムを少しづつ作成していきたいと思います。
この記事は、Gushwell's C# Programming Pageで公開したものを加筆・修正したものです。