編集履歴

回答編集履歴

表現の微調整

2020/03/11 10:55

投稿

スコア1083

test CHANGED Viewed

@@ -180,7 +180,7 @@
-上のコードからcalculate()メソッドを削除しオペランドスタックをリストにかえてリストへ演算子を追加すると、逆ポーランド記法を生成できます。せっかくだから、逆ポーランド記法を生成して評価する関数型の実装を紹介します。
+上のコードからcalculate()メソッドを削除しオペランドスタックをリストにかえてリストへ演算子を追加すると、逆ポーランド記法を生成できます。せっかくだから、逆ポーランド記法を生成して評価する関数型コードを書いてみました。
@@ -328,7 +328,7 @@
-上で作成したList<Character>を入力にする逆ポーランド記法の評価器（関数）を定義。
+上で作成したList<Character>を入力する逆ポーランド記法の評価器（関数）を定義。

逆ポーランド記法（追記）

2020/03/11 10:55

投稿

xebme

スコア1083

test CHANGED Viewed

@@ -171,3 +171,267 @@
 - [Parsing/RPN calculator algorithm](https://rosettacode.org/wiki/Parsing/RPN_calculator_algorithm)
 - [Parsing/Shunting-yard algorithm](https://rosettacode.org/wiki/Parsing/Shunting-yard_algorithm)
+##
+**逆ポーランド記法（追記）**
+上のコードからcalculate()メソッドを削除しオペランドスタックをリストにかえてリストへ演算子を追加すると、逆ポーランド記法を生成できます。せっかくだから、逆ポーランド記法を生成して評価する関数型の実装を紹介します。
+演算に除算`/`を追加して優先度を以下のように決定。
+```Java
+static Function<Character,Integer> priority =
+  operator -> (operator == '*' || operator == '/') ? 2
+            : (operator == '+' || operator == '-') ? 1 : 0;
+static BiFunction<Character,Character,Boolean> preceding =
+  (op1,op2) -> priority.apply(op1) >= priority.apply(op2);
+```
+逆ポーランド記法の生成器（関数）を定義する。逆ポーランド記法として出力されるのはList<Character>。
+```Java
+static Function<String,List<Character>> toRpn = expression -> {
+  Deque<Character> operators = new LinkedList<>(); // キャプチャされる。
+  List<Character> rpnList = expression.chars()
+    .mapToObj(c -> Character.valueOf((char) c))
+    .collect(
+      ArrayList::new,
+      (accList, token) -> {
+        switch (token) {
+          case ' ':
+            break;
+          case '(':
+            operators.push(token);
+            break;
+          case ')':
+            while (!operators.isEmpty()) {
+              char operator = operators.pop();
+              if (operator == '(') {
+                break;
+              }
+              accList.add(operator);
+            }
+            break;
+          case '0':
+          case '1':
+          case '2':
+          case '3':
+          case '4':
+          case '5':
+          case '6':
+          case '7':
+          case '8':
+          case '9':
+            accList.add(token);
+            break;
+          case '+':
+          case '-':
+          case '*'
+          case '/':
+            if (!operators.isEmpty() && preceding.apply(operators.peek(), token)) {
+              accList.add(operators.pop());
+            }
+            operators.push(token);
+            break;
+          default: //
+            throw new RuntimeException("Invalid token : '" + token + "' in '" + expression + "'");
+        }
+      },
+      List::addAll);
+  while (!operators.isEmpty()) {
+    rpnList.add(operators.pop());
+  }
+  return rpnList;
+};
+```
+**逆ポーランド記法の評価**
+上で作成したList<Character>を入力にする逆ポーランド記法の評価器（関数）を定義。
+```Java
+static Function<List<Character>,Integer> evalRpn = rpn -> {
+  Deque<Integer> result =
+    rpn.stream()
+       .collect(
+          LinkedList::new,
+          (operandStack, token) -> {
+            switch (token) {
+              case '0':
+              case '1':
+              case '2':
+              case '3':
+              case '4':
+              case '5':
+              case '6':
+              case '7':
+              case '8':
+              case '9':
+                operandStack.push(token - '0');
+                break;
+              case '+':
+                operandStack.push(operandStack.pop() + operandStack.pop());
+                break;
+              case '-':
+                operandStack.push(-operandStack.pop() + operandStack.pop());
+                break;
+              case '*':
+                operandStack.push(operandStack.pop() * operandStack.pop());
+                break;
+              case '/':
+                operandStack.push((int)(1d / operandStack.pop() * operandStack.pop()));
+                break;
+            }
+          },
+         Deque::addAll);
+  return result.pop();
+ };
+```
+逆ポーランド記法の生成と評価を合成。
+```Java
+static Function<String,Integer> eval = toRpn.andThen(evalRpn);
+```
+利用方法。
+```Java
+String expression = "2 * (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)";
+int result = eval.apply(expression);
+System.out.println(expression + " = " + result);
+```