C#
アルゴリズム
C#小品集シリース

C#:逆ポーランド記法を利用した数式の計算(6) 最後の仕上げ

More than 1 year has passed since last update.

これまでの記事

(1) 逆ポーランド記法の計算
(2) 数式をトークンに分割する
(3) ReversePolishNotationクラスを改良する
(4) Contextクラスを定義する
(5) Interpreterパターンで数式を解析する

Expressionクラス

いよいよ、大詰めです。このシリーズ最終回です。
これまで作成してきた部品群を使い、計算を行うクラスExpressionクラスを実装します。

    public class Expression {
        public static decimal Calculate(string exp) {
            // 数式を逆ポーランド記法へ変換
            ReversePolishNotation rpn = ConvertToRpn(exp);
            // 逆ポーランド記法の式を計算する
            return RpnCalculator.Calculate(rpn);
        }

        // 数式を逆ポーランド記法へ変換
        private static ReversePolishNotation ConvertToRpn(string exp) {
            var context = new Context(exp);
            var node = new ExpressionNode();
            node.Parse(context);
            if (!context.IsTerminate)
                throw new ArithmeticException("正しい式ではありません");
            return context.Notation;
        }
    }

コード読んでもらえればわかると思いますが、簡単に説明しておきます。

Calculateから呼び出される下位メソッドであるConvertToRpnメソッドでは、ContextオブジェクトとExpressionNodeオブジェクトを生成し、ExpressionNodeオブジェクトのParseメソッドを呼び出します。
Parseメソッドから処理が戻ってくると、逆ポーランド記法に変換した結果がContexctオブジェクトのNotationプロパティに入っていますので、このNotationプロパティの値を返していいます。

Calculateメソッドでは、このオブジェクトをRpnCalculator.Calculateメソッドに渡して計算しています。

Mainメソッドの実装

最後にMainメソッドを書いて出来上がりです。
通常の数式をコンソールから入力し、それを計算し、結果を表示するプログラムを書いてみます。
空行を入れるまで、数式入力、計算、結果出力を繰り返しています。

    class Program {
        static void Main(string[] args) {
            while (true) {
                var exp = Console.ReadLine();
                if (exp.Length == 0)
                    break;
                try {
                    var ans = Expression.Calculate(exp);
                    Console.WriteLine($"=> {exp} = {ans}");
                } catch (Exception ex) {
                    Console.WriteLine(ex.ToString());
                }
            }
        }
    }

実行例

5 * (3 + 7) + 50
=> 5 * (3 + 7) + 50 = 100
(200 - 100) / (10 + 10)
=> (200 - 100) / (10 + 10) = 5
((2 + 3) * (5 + -2)) / -3
=> ((2 + 3) * (5 + -2)) / -3 = -5
1290 * 1.08
=> 1290 * 1.08 = 1393.20

これまで掲載してきた「プログラム小品集」シリーズの中では、かなり大きいプログラムとなりましたが、一つ一つのクラスは小さめのものばかりですので、興味のある方は、頑張って読んでみてください。

すべてのコード

最後に、すべてのコードを掲載します。

using System;

namespace Rpn.App {
    class Program {
        static void Main(string[] args) {
            while (true) {
                var exp = Console.ReadLine();
                if (exp.Length == 0)
                    break;
                try {
                    var ans = Expression.Calculate(exp);
                    Console.WriteLine($"=> {exp} = {ans}");
                } catch (Exception ex) {
                    Console.WriteLine(ex.ToString());
                }
            }
        }
    }
}
using System;

namespace Rpn.App {
    public class Expression {
        public static decimal Calculate(string exp) {
            // 数式を逆ポーランド記法へ変換
            ReversePolishNotation rpn = ConvertToRpn(exp);
            // 逆ポーランド記法の式を計算する
            return RpnCalculator.Calculate(rpn);
        }

        // 数式を逆ポーランド記法へ変換
        private static ReversePolishNotation ConvertToRpn(string exp) {
            var context = new Context(exp);
            var node = new ExpressionNode();
            node.Parse(context);
            if (!context.IsTerminate)
                throw new ArithmeticException("正しい式ではありません");
            return context.Notation;
        }
    }
}
using System;
using System.Collections.Generic;
using System.Linq;

namespace Rpn.App {

    public class ReversePolishNotation {
        private List<string> _tokens = new List<string>();

        public IEnumerable<string> Tokens => _tokens;


        public ReversePolishNotation(string exp = "") {
            var tokens = exp.Split(' ').Where(s => s != "");
            _tokens = tokens.ToList();
        }

        public void Add(string token) {
            _tokens.Add(token);
        }

        public override string ToString() {
            return String.Join(" ", Tokens.ToArray());
        }
    }
}
using System;
using System.Collections.Generic;

namespace Rpn.App {
    // shiracamusさんのコードを採用
    // https://qiita.com/gushwell/items/a40f4119a35a1e6d7622 のコメント
    public class RpnCalculator {
        static Dictionary<string, Func<decimal, decimal, decimal>> binaryOperators =
            new Dictionary<string, Func<decimal, decimal, decimal>>() {
                ["+"] = (a, b) => a + b,
                ["-"] = (a, b) => a - b,
                ["*"] = (a, b) => a * b,
                ["/"] = (a, b) => a / b,
            };

        // 後置記法を計算する
        public static decimal Calculate(ReversePolishNotation rpn) {
            Stack<object> stack = new Stack<object>();
            foreach (var token in rpn.Tokens) {
                if (binaryOperators.ContainsKey(token)) {
                    var b = (decimal)stack.Pop();
                    var a = (decimal)stack.Pop();
                    var c = binaryOperators[token](a, b);
                    stack.Push(c);
                } else {
                    stack.Push(decimal.Parse(token));
                }
            }
            return (decimal)stack.Pop();
        }
    }
}
using System;

namespace Rpn.App {
    public class Context {
        private Tokenizer _tokenizer;

        public ReversePolishNotation Notation { get; } = new ReversePolishNotation();

        public bool IsTerminate { get; set; } = false;

        public Context(string exp) {
            _tokenizer = new Tokenizer(exp);
            _tokenizer.MoveNext();
        }

        public bool MoveNext() {
            if (_tokenizer.MoveNext()) 
                return true;
            IsTerminate = true;
            return false;            
        }

        public string CurrentToken {
            get { return _tokenizer.Current; }
        }
    }
}
using System;
using System.Collections.Generic;
using System.Linq;

namespace Rpn.App {

    // Tokenに分解する
    public class Tokenizer {
        private string _expression;

        IEnumerator<string> _ite;

        public Tokenizer(string exp) {
            _expression = exp;
            _ite = GetTokens().GetEnumerator();
        }

        public bool MoveNext() {
            return _ite.MoveNext();
        }

        public string Current {
            get { return _ite.Current; }
        }

        private IEnumerable<string> GetTokens() {
            char c = NextChar();
            var token = "";
            while (c != (char)0) {
                if (char.IsDigit(c)) {
                    token += c;
                } else if (c == '.' && token.All(x => x != '.')) {
                    token += c;
                } else {
                    if (token != "")
                        yield return token;
                    token = "";
                    if (IsSymbol(c))
                        yield return c.ToString();
                    else if (c != ' ')
                        throw new ArithmeticException("正しい式ではありません");
                }
                c = NextChar();
            }
            if (token != "")
                yield return token;
        }

        private static bool IsSymbol(char c) {
            if (c == '+' || c == '-' || c == '*' || c == '/' ||
                c == '(' || c == ')')
                return true;
            return false;
        }

        private int _currentIndex = 0;

        private char NextChar() {
            if (_currentIndex < _expression.Length)
                return _expression[_currentIndex++];
            return (char)0;
        }
    }
}
using System;
using System.Collections.Generic;

namespace Rpn.App {

    public abstract class Node {
        public abstract void Parse(Context context);
        public static bool IsOperator(char c) {
            return (c == '+' || c == '-' || c == '*' || c == '/');
        }

        public static bool IsParenthesis(char c) {
            return (c == '(' || c == ')');
        }

        public static bool IsSign(char c) {
            return (c == '-' || c == '+');
        }

        public static int GetSign(string s) {
            if (s[0] == '-')
                return -1;
            return 1;
        }
    }

    public class SignedNumberNode : Node {
        public override void Parse(Context context) {
            var token = context.CurrentToken;
            int sign = 1;
            IEnumerable<char> nstr = token;
            if (IsSign(token[0])) {
                sign = GetSign(token);
                context.MoveNext();
                token += context.CurrentToken;
            }
            if (decimal.TryParse(token, out var num)) {
                context.Notation.Add(token);
            } else {
                throw new ArithmeticException("正しい式ではありません");
            }
            context.MoveNext();
        }
    }

    public class FactorNode : Node {
        public override void Parse(Context context) {
            var token = context.CurrentToken;
            if (token == "(") {
                context.MoveNext();
                Node node = new ExpressionNode();
                node.Parse(context);
                context.MoveNext();
            } else {
                Node node = new SignedNumberNode();
                node.Parse(context);
            }
        }
    }

    public class DivTermNode : Node {
        public override void Parse(Context context) {
            Node node1 = new FactorNode();
            node1.Parse(context);
            string token = context.CurrentToken;
            while (token == "/") {
                context.MoveNext();
                Node node2 = new FactorNode();
                node2.Parse(context);
                context.Notation.Add(token);
                token = context.CurrentToken;
            }
        }
    }

    public class TermNode : Node {
        public override void Parse(Context context) {
            Node node1 = new DivTermNode();
            node1.Parse(context);
            string token = context.CurrentToken;
            while (token == "*") {
                context.MoveNext();
                Node node2 = new DivTermNode();
                node2.Parse(context);
                context.Notation.Add(token);
                token = context.CurrentToken;
            }
        }
    }

    public class ExpressionNode : Node {
        public override void Parse(Context context) {
            Node node1 = new TermNode();
            node1.Parse(context);
            var token = context.CurrentToken;
            while (token == "+" || token == "-") {
                context.MoveNext();
                Node node2 = new TermNode();
                node2.Parse(context);
                context.Notation.Add(token);
                token = context.CurrentToken;
            }
        }
    }
}

この記事は、Gushwell's C# Programming Pageで公開したものを大幅に加筆・修正したものです。