LoginSignup
1
4

More than 5 years have passed since last update.

@gushwell(出井 秀行)

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

Last updated at Posted at 2017-12-05

記事一覧

逆ポーランド記法を利用した数式の計算(1) 逆ポーランド記法の計算
逆ポーランド記法を利用した数式の計算(2) 数式をトークンに分割する
逆ポーランド記法を利用した数式の計算(3) ReversePolishNotationクラスを改良する
逆ポーランド記法を利用した数式の計算(4) Contextクラスを定義する
逆ポーランド記法を利用した数式の計算(5) Interpreterパターンで数式を解析する
逆ポーランド記法を利用した数式の計算(6) 最後の仕上げ ← 当記事

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で公開したものを大幅に加筆・修正したものです。

1
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
4