回答編集履歴
2
表現の微調整
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
逆ポーランド記法（追記）
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
|
+
```
|