teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

2

表現の微調整

2020/03/11 10:55

投稿

xebme
xebme

スコア1109

answer CHANGED
@@ -89,7 +89,7 @@
89
89
  ##
90
90
  **逆ポーランド記法(追記)**
91
91
 
92
- 上のコードからcalculate()メソッドを削除しオペランドスタックをリストにかえてリストへ演算子を追加すると、逆ポーランド記法を生成できます。せっかくだから、逆ポーランド記法を生成して評価する関数型の実装紹介し
92
+ 上のコードからcalculate()メソッドを削除しオペランドスタックをリストにかえてリストへ演算子を追加すると、逆ポーランド記法を生成できます。せっかくだから、逆ポーランド記法を生成して評価する関数型コード書いてみした
93
93
 
94
94
  演算に除算`/`を追加して優先度を以下のように決定。
95
95
 
@@ -163,7 +163,7 @@
163
163
 
164
164
  **逆ポーランド記法の評価**
165
165
 
166
- 上で作成したList<Character>を入力する逆ポーランド記法の評価器(関数)を定義。
166
+ 上で作成したList<Character>を入力する逆ポーランド記法の評価器(関数)を定義。
167
167
 
168
168
  ```Java
169
169
  static Function<List<Character>,Integer> evalRpn = rpn -> {

1

逆ポーランド記法(追記)

2020/03/11 10:55

投稿

xebme
xebme

スコア1109

answer CHANGED
@@ -84,4 +84,136 @@
84
84
  - [逆ポーランド記法](https://ja.wikipedia.org/wiki/逆ポーランド記法)
85
85
  - [操車場アルゴリズム](https://ja.wikipedia.org/wiki/操車場アルゴリズム)
86
86
  - [Parsing/RPN calculator algorithm](https://rosettacode.org/wiki/Parsing/RPN_calculator_algorithm)
87
- - [Parsing/Shunting-yard algorithm](https://rosettacode.org/wiki/Parsing/Shunting-yard_algorithm)
87
+ - [Parsing/Shunting-yard algorithm](https://rosettacode.org/wiki/Parsing/Shunting-yard_algorithm)
88
+
89
+ ##
90
+ **逆ポーランド記法(追記)**
91
+
92
+ 上のコードからcalculate()メソッドを削除しオペランドスタックをリストにかえてリストへ演算子を追加すると、逆ポーランド記法を生成できます。せっかくだから、逆ポーランド記法を生成して評価する関数型の実装を紹介します。
93
+
94
+ 演算に除算`/`を追加して優先度を以下のように決定。
95
+
96
+ ```Java
97
+ static Function<Character,Integer> priority =
98
+ operator -> (operator == '*' || operator == '/') ? 2
99
+ : (operator == '+' || operator == '-') ? 1 : 0;
100
+
101
+ static BiFunction<Character,Character,Boolean> preceding =
102
+ (op1,op2) -> priority.apply(op1) >= priority.apply(op2);
103
+ ```
104
+
105
+ 逆ポーランド記法の生成器(関数)を定義する。逆ポーランド記法として出力されるのはList<Character>。
106
+
107
+ ```Java
108
+ static Function<String,List<Character>> toRpn = expression -> {
109
+ Deque<Character> operators = new LinkedList<>(); // キャプチャされる。
110
+ List<Character> rpnList = expression.chars()
111
+ .mapToObj(c -> Character.valueOf((char) c))
112
+ .collect(
113
+ ArrayList::new,
114
+ (accList, token) -> {
115
+ switch (token) {
116
+ case ' ':
117
+ break;
118
+ case '(':
119
+ operators.push(token);
120
+ break;
121
+ case ')':
122
+ while (!operators.isEmpty()) {
123
+ char operator = operators.pop();
124
+ if (operator == '(') {
125
+ break;
126
+ }
127
+ accList.add(operator);
128
+ }
129
+ break;
130
+ case '0':
131
+ case '1':
132
+ case '2':
133
+ case '3':
134
+ case '4':
135
+ case '5':
136
+ case '6':
137
+ case '7':
138
+ case '8':
139
+ case '9':
140
+ accList.add(token);
141
+ break;
142
+ case '+':
143
+ case '-':
144
+ case '*'
145
+ case '/':
146
+ if (!operators.isEmpty() && preceding.apply(operators.peek(), token)) {
147
+ accList.add(operators.pop());
148
+ }
149
+ operators.push(token);
150
+ break;
151
+ default: //
152
+ throw new RuntimeException("Invalid token : '" + token + "' in '" + expression + "'");
153
+ }
154
+ },
155
+ List::addAll);
156
+ while (!operators.isEmpty()) {
157
+ rpnList.add(operators.pop());
158
+ }
159
+ return rpnList;
160
+ };
161
+
162
+ ```
163
+
164
+ **逆ポーランド記法の評価**
165
+
166
+ 上で作成したList<Character>を入力にする逆ポーランド記法の評価器(関数)を定義。
167
+
168
+ ```Java
169
+ static Function<List<Character>,Integer> evalRpn = rpn -> {
170
+ Deque<Integer> result =
171
+ rpn.stream()
172
+ .collect(
173
+ LinkedList::new,
174
+ (operandStack, token) -> {
175
+ switch (token) {
176
+ case '0':
177
+ case '1':
178
+ case '2':
179
+ case '3':
180
+ case '4':
181
+ case '5':
182
+ case '6':
183
+ case '7':
184
+ case '8':
185
+ case '9':
186
+ operandStack.push(token - '0');
187
+ break;
188
+ case '+':
189
+ operandStack.push(operandStack.pop() + operandStack.pop());
190
+ break;
191
+ case '-':
192
+ operandStack.push(-operandStack.pop() + operandStack.pop());
193
+ break;
194
+ case '*':
195
+ operandStack.push(operandStack.pop() * operandStack.pop());
196
+ break;
197
+ case '/':
198
+ operandStack.push((int)(1d / operandStack.pop() * operandStack.pop()));
199
+ break;
200
+ }
201
+ },
202
+ Deque::addAll);
203
+ return result.pop();
204
+ };
205
+ ```
206
+
207
+ 逆ポーランド記法の生成と評価を合成。
208
+
209
+ ```Java
210
+ static Function<String,Integer> eval = toRpn.andThen(evalRpn);
211
+ ```
212
+
213
+ 利用方法。
214
+
215
+ ```Java
216
+ String expression = "2 * (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)";
217
+ int result = eval.apply(expression);
218
+ System.out.println(expression + " = " + result);
219
+ ```