teratail
回答率
85.47%
質問するログイン新規登録
トップ標準入力に関する質問Java言語で標準入力で受け取った中置記法の数式を逆ポーランド記法に変換したい。

編集履歴

回答編集履歴

9

係数優先モード指定追加

2023/02/12 19:38

投稿

jimbe
jimbe

スコア12659

test CHANGED
@@ -1,5 +1,8 @@
1
1
  リストを配列で定義し、スタックはそのリストを利用するように定義、正規表現をコード化、内部クラスの殆どを展開しました。
2
2
  簡単になったとは思えませんが…。
3
+
4
+ 係数優先モード指定追加。 `6/2(1+2)` の結果を選べます。(true なら 1、 false なら 9)
5
+
3
6
  ```java
4
7
  class List {
5
8
  private String[] values = new String[0];
@@ -32,6 +35,10 @@
32
35
  * @param i インデックス(0 ～ size()-1)
33
36
  * @return データ */
34
37
  String get(int i) { return values[i]; }
38
+ /** i 番目を変更
39
+ * @param i インデックス(0 ～ size()-1)
40
+ * @param v データ */
41
+ void set(int i, String v) { values[i] = v; }
35
42
  /** 件数
36
43
  * @return 件数 */
37
44
  int size() { return size; }
@@ -62,9 +69,9 @@
62
69
 
63
70
  public class Main {
64
71
  public static void main(String[] args) {
65
- String[] testdata = { "1+2.5*-3", "100*50/20", "(20+30)*5", "2(3+5)/4", "1+(2(3+((5/2)-2)))" };
72
+ String[] testdata = { "1+2.5*-3", "100*50/20", "(20+30)*5", "2(3+5)/4", "1+(2(3+((5/2)-2)))", "6/2(1+2)" };
66
73
  for(String formula : testdata) {
67
- RPN rpn = new RPN(formula);
74
+ RPN rpn = new RPN(formula, true);
68
75
  System.out.println(rpn + "=" + rpn.calc());
69
76
  }
70
77
  }
@@ -80,7 +87,7 @@
80
87
  this.formula = formula;
81
88
  }
82
89
 
83
- List translate() {
90
+ List translate(boolean coefficientPriorityMode) {
84
91
  int mode = 0;
85
92
  while(!isEnd()) {
86
93
  if(mode == 0) {
@@ -95,7 +102,7 @@
95
102
  if(op.equals(")")) {
96
103
  putOp(op);
97
104
  } else {
98
- if(op.equals("(")) putOp("*");
105
+ if(op.equals("(")) putOp(coefficientPriorityMode ? "**" : "*");
99
106
  putOp(op);
100
107
  mode = 0;
101
108
  }
@@ -135,6 +142,7 @@
135
142
  stack.push(op);
136
143
  }
137
144
  private int getPri(String op) {
145
+ if(op.equals("**")) return 3;
138
146
  if(op.equals("*") || op.equals("/")) return 2;
139
147
  if(op.equals("+") || op.equals("-")) return 1;
140
148
  return 0;
@@ -144,6 +152,7 @@
144
152
  }
145
153
  private List complete() {
146
154
  while(!stack.isEmpty()) list.add(stack.pop());
155
+ for(int i=0; i<list.size(); i++) if(list.get(i).equals("**")) list.set(i, "*");
147
156
  return new List(list);
148
157
  }
149
158
  }
@@ -151,9 +160,9 @@
151
160
  private final String formula;
152
161
  private List list;
153
162
 
154
- RPN(String formula) {
163
+ RPN(String formula, boolean coefficientPriorityMode) {
155
164
  this.formula = formula;
156
- list = new Translator(formula).translate();
165
+ list = new Translator(formula).translate(coefficientPriorityMode);
157
166
  }
158
167
 
159
168
  String calc() {
@@ -196,4 +205,5 @@
196
205
  (20+30)*5=[20, 30, +, 5, *]=250.0
197
206
  2(3+5)/4=[2, 3, 5, +, *, 4, /]=4.0
198
207
  1+(2(3+((5/2)-2)))=[1, 2, 3, 5, 2, /, 2, -, +, *, +]=8.0
208
+ 6/2(1+2)=[6, 2, 1, 2, +, *, /]=1.0
199
209
  ```

8

修正

2023/02/12 05:08

投稿

jimbe
jimbe

スコア12659

test CHANGED
@@ -1,4 +1,4 @@
1
- リストを配列で定義し、スタックはそのリストを利用するように定義、正規表現をコード化、 enum を通常クラスにしました。
1
+ リストを配列で定義し、スタックはそのリストを利用するように定義、正規表現をコード化、内部クラスの殆どを展開しました。
2
2
  簡単になったとは思えませんが…。
3
3
  ```java
4
4
  class List {

7

内部クラス展開

2023/02/12 05:07

投稿

jimbe
jimbe

スコア12659

test CHANGED
@@ -1,20 +1,20 @@
1
1
  リストを配列で定義し、スタックはそのリストを利用するように定義、正規表現をコード化、 enum を通常クラスにしました。
2
2
  簡単になったとは思えませんが…。
3
3
  ```java
4
- class List<T> {
4
+ class List {
5
- private Object[] values = new Object[0];
5
+ private String[] values = new String[0];
6
6
  private int size = 0;
7
7
  List() {}
8
- List(List<T> org) {
8
+ List(List org) {
9
9
  size = org.size;
10
- values = new Object[org.values.length];
10
+ values = new String[org.values.length];
11
11
  for(int i=0; i<size; i++) values[i] = org.values[i];
12
12
  }
13
13
  /** 最後に追加
14
14
  * @param v 追加するデータ */
15
- void add(T v) {
15
+ void add(String v) {
16
16
  if(size == values.length) {
17
- Object[] newValues = new Object[values.length + 10];
17
+ String[] newValues = new String[values.length + 10];
18
18
  for(int i=0; i<size; i++) newValues[i] = values[i];
19
19
  values = newValues;
20
20
  }
@@ -23,15 +23,15 @@
23
23
  /** i 番目を削除
24
24
  * @param i インデックス(0 ～ size()-1)
25
25
  * @return 削除したデータ */
26
- T remove(int i) {
26
+ String remove(int i) {
27
- T v = (T)values[i];
27
+ String v = values[i];
28
28
  for(size--; i<size; i++) values[i] = values[i+1];
29
29
  return v;
30
30
  }
31
31
  /** i 番目を取得
32
32
  * @param i インデックス(0 ～ size()-1)
33
33
  * @return データ */
34
- T get(int i) { return (T)values[i]; }
34
+ String get(int i) { return values[i]; }
35
35
  /** 件数
36
36
  * @return 件数 */
37
37
  int size() { return size; }
@@ -44,17 +44,17 @@
44
44
  }
45
45
  }
46
46
 
47
- class Stack<T> {
47
+ class Stack {
48
- private List<T> list = new List<>();
48
+ private List list = new List();
49
49
  /** トップに追加
50
50
  * @param v 追加するデータ */
51
- void push(T v) { list.add(v); }
51
+ void push(String v) { list.add(v); }
52
52
  /** トップから取り出し
53
53
  * @return データ */
54
- T pop() { return list.remove(list.size()-1); }
54
+ String pop() { return list.remove(list.size()-1); }
55
55
  /** トップを確認
56
56
  * @return データ */
57
- T peek() { return list.get(list.size()-1); }
57
+ String peek() { return list.get(list.size()-1); }
58
58
  /** 空判定
59
59
  * @return 空なら true */
60
60
  boolean isEmpty() { return list.size() == 0; }
@@ -70,165 +70,116 @@
70
70
  }
71
71
 
72
72
  private static class RPN {
73
+ private static class Translator {
74
+ private final String formula;
73
- private interface Element {
75
+ private int index;
74
- void operate(Stack<String> stack);
76
+ private Stack stack = new Stack();
75
- }
77
+ private List list = new List();
76
78
 
77
- private static class Value implements Element {
78
- private final String v;
79
- Value(String v) {
79
+ Translator(String formula) {
80
- this.v = v;
80
+ this.formula = formula;
81
81
  }
82
+
83
+ List translate() {
84
+ int mode = 0;
85
+ while(!isEnd()) {
86
+ if(mode == 0) {
87
+ if(getChar() == '(') {
88
+ putOp(nextOperator());
89
+ } else {
90
+ putValue(nextNumber());
82
- @Override
91
+ mode = 1;
92
+ }
93
+ } else {
94
+ String op = nextOperator();
95
+ if(op.equals(")")) {
96
+ putOp(op);
97
+ } else {
83
- public void operate(Stack<String> stack) {
98
+ if(op.equals("(")) putOp("*");
99
+ putOp(op);
100
+ mode = 0;
101
+ }
102
+ }
103
+ }
84
- stack.push(v);
104
+ return complete();
85
105
  }
106
+
107
+ private boolean isEnd() { return index >= formula.length(); }
108
+ private char getChar() { return formula.charAt(index); }
109
+ private String nextOperator() {
110
+ String op = "" + formula.charAt(index++);
111
+ if("+-*/()".indexOf(op.charAt(0)) < 0) throw new IllegalArgumentException("Operator Error: index=" + index);
86
- @Override
112
+ return op;
113
+ }
87
- public String toString() {
114
+ private String nextNumber() {
115
+ int j, i = index + (formula.charAt(index)=='-'?1:0);
116
+ for(j=0; i<formula.length() && ('0'<=formula.charAt(i) && formula.charAt(i)<='9'); i++, j++);
117
+ if(j > 0 && i < formula.length() && formula.charAt(i) == '.') {
118
+ for(i++, j=0; i<formula.length() && ('0'<=formula.charAt(i) && formula.charAt(i)<='9'); i++, j++);
119
+ }
120
+ if(j == 0) throw new IllegalArgumentException("Number Error: index=" + index);
121
+ String v = formula.substring(index, i);
122
+ index = i;
88
123
  return v;
89
124
  }
90
- }
91
125
 
92
- private static class Operator implements Element {
93
- static Operator PLS = new Operator("+",1) { @Override protected double calc(double a, double b) { return a + b; } };
94
- static Operator MIN = new Operator("-",1) { @Override protected double calc(double a, double b) { return a - b; } };
95
- static Operator MUL = new Operator("*",2) { @Override protected double calc(double a, double b) { return a * b; } };
96
- static Operator DIV = new Operator("/",2) { @Override protected double calc(double a, double b) { return a / b; } };
97
- static Operator BS = new Operator("(",0);
98
- static Operator BE = new Operator(")",0);
99
-
100
- private static Operator[] values = { PLS, MIN, MUL, DIV, BS, BE };
101
-
102
- private final String text;
126
+ private void putOp(String op) {
103
- private final int pri;
127
+ if(op.equals(")")) {
128
+ while(!stack.isEmpty() && !(op=stack.pop()).equals("(")) list.add(op.toString());
129
+ if(!op.equals("(")) throw new IllegalStateException("Formula Error: Unmatched parentheses.");
130
+ return;
131
+ }
104
- private Operator(String text, int pri) {
132
+ if(!op.equals("(")) {
105
- this.text = text;
133
+ while(!stack.isEmpty() && getPri(stack.peek()) >= getPri(op)) list.add(stack.pop());
134
+ }
106
- this.pri = pri;
135
+ stack.push(op);
107
136
  }
108
-
109
- static Operator of(char c) {
137
+ private int getPri(String op) {
138
+ if(op.equals("*") || op.equals("/")) return 2;
110
- for(Operator ope : values) if(ope.text.charAt(0) == c) return ope;
139
+ if(op.equals("+") || op.equals("-")) return 1;
111
- return null;
140
+ return 0;
112
141
  }
113
-
114
- @Override
115
- public void operate(Stack<String> stack) {
142
+ private void putValue(String v) {
116
- double b = Double.parseDouble(stack.pop());
117
- double a = Double.parseDouble(stack.pop());
118
- stack.push("" + calc(a, b));
143
+ list.add(v);
119
144
  }
120
-
121
- protected double calc(double a, double b) {
122
- throw new UnsupportedOperationException();
123
- }
124
-
125
- @Override
126
- public String toString() {
127
- return text;
128
- }
129
- }
130
-
131
- private static class Translator {
132
- private static class Source {
133
- private final String formula;
134
- private int index;
135
-
136
- Source(String formula) {
137
- this.formula = formula;
138
- }
139
-
140
- boolean isEnd() { return index >= formula.length(); }
141
- char getChar() { return formula.charAt(index); }
142
- Operator nextOperator() {
143
- Operator op = Operator.of(formula.charAt(index++));
144
- if(op == null) throw new IllegalArgumentException("Operator Error: index=" + index);
145
- return op;
146
- }
147
- Value nextNumber() {
148
- int j, i = index + (formula.charAt(index)=='-'?1:0);
149
- for(j=0; i<formula.length() && ('0'<=formula.charAt(i) && formula.charAt(i)<='9'); i++, j++);
150
- if(j > 0 && i < formula.length() && formula.charAt(i) == '.') {
151
- for(i++, j=0; i<formula.length() && ('0'<=formula.charAt(i) && formula.charAt(i)<='9'); i++, j++);
152
- }
153
- if(j == 0) throw new IllegalArgumentException("Number Error: index=" + index);
154
- Value v = new Value(formula.substring(index, i));
155
- index = i;
156
- return v;
157
- }
158
- }
159
-
160
- private static class Destination {
161
- private Stack<Operator> stack = new Stack<>();
162
- private List<Element> list = new List<>();
163
-
164
- void put(Operator op) {
165
- if(op == Operator.BE) {
166
- while(!stack.isEmpty() && (op=stack.pop()) != Operator.BS) list.add(op);
167
- if(op != Operator.BS) throw new IllegalStateException("Formula Error: Unmatched parentheses.");
168
- return;
169
- }
170
- if(op != Operator.BS) {
171
- while(!stack.isEmpty() && stack.peek().pri >= op.pri) list.add(stack.pop());
172
- }
173
- stack.push(op);
174
- }
175
- void put(Value v) {
176
- list.add(v);
177
- }
178
- List<Element> complete() {
145
+ private List complete() {
179
- while(!stack.isEmpty()) list.add(stack.pop());
146
+ while(!stack.isEmpty()) list.add(stack.pop());
180
- return new List<>(list);
147
+ return new List(list);
181
- }
182
- }
183
-
184
- private static class Mode {
185
- static Mode NUM = new Mode() {
186
- Mode translate(Source src, Destination dst) {
187
- if(src.getChar() == '(') {
188
- dst.put(src.nextOperator());
189
- return this;
190
- }
191
- dst.put(src.nextNumber());
192
- return OP;
193
- }
194
- };
195
- static Mode OP = new Mode() {
196
- Mode translate(Source src, Destination dst) {
197
- Operator op = src.nextOperator();
198
- if(op == Operator.BE) {
199
- dst.put(op);
200
- return this;
201
- }
202
- if(op == Operator.BS) dst.put(Operator.MUL);
203
- dst.put(op);
204
- return NUM;
205
- }
206
- };
207
-
208
- private Mode() {}
209
- Mode translate(Source src, Destination dst) { return null; };
210
- }
211
-
212
- static List<Element> translate(String formula) {
213
- Mode mode = Mode.NUM;
214
- Source src = new Source(formula);
215
- Destination dst = new Destination();
216
- while(!src.isEnd()) mode = mode.translate(src, dst);
217
- return dst.complete();
218
148
  }
219
149
  }
220
150
 
221
151
  private final String formula;
222
- private List<Element> list;
152
+ private List list;
223
153
 
224
154
  RPN(String formula) {
225
155
  this.formula = formula;
226
- list = Translator.translate(formula);
156
+ list = new Translator(formula).translate();
227
157
  }
228
158
 
229
159
  String calc() {
230
- Stack<String> stack = new Stack<>();
160
+ Stack stack = new Stack();
231
- for(int i=0; i<list.size(); i++) list.get(i).operate(stack);
161
+ for(int i=0; i<list.size(); i++) {
162
+ String s = list.get(i);
163
+ if(s.equals("+")) {
164
+ double b = Double.parseDouble(stack.pop());
165
+ double a = Double.parseDouble(stack.pop());
166
+ stack.push("" + (a + b));
167
+ } else if(s.equals("-")) {
168
+ double b = Double.parseDouble(stack.pop());
169
+ double a = Double.parseDouble(stack.pop());
170
+ stack.push("" + (a - b));
171
+ } else if(s.equals("*")) {
172
+ double b = Double.parseDouble(stack.pop());
173
+ double a = Double.parseDouble(stack.pop());
174
+ stack.push("" + (a * b));
175
+ } else if(s.equals("/")) {
176
+ double b = Double.parseDouble(stack.pop());
177
+ double a = Double.parseDouble(stack.pop());
178
+ stack.push("" + (a / b));
179
+ } else {
180
+ stack.push(s);
181
+ }
182
+ }
232
183
  return stack.pop();
233
184
  }
234
185
 

6

修正

2023/02/11 04:16

投稿

jimbe
jimbe

スコア12659

test CHANGED
@@ -1,4 +1,4 @@
1
- リストを配列で定義し、スタックはそのリストを利用するように定義、正規表現をコード化しました。
1
+ リストを配列で定義し、スタックはそのリストを利用するように定義、正規表現をコード化、 enum を通常クラスにしました。
2
2
  簡単になったとは思えませんが…。
3
3
  ```java
4
4
  class List<T> {

5

enum を通常クラス化

2023/02/11 04:15

投稿

jimbe
jimbe

スコア12659

test CHANGED
@@ -89,23 +89,25 @@
89
89
  }
90
90
  }
91
91
 
92
- private enum Operator implements Element {
92
+ private static class Operator implements Element {
93
- PLS("+",1) { @Override protected double calc(double a, double b) { return a + b; } },
93
+ static Operator PLS = new Operator("+",1) { @Override protected double calc(double a, double b) { return a + b; } };
94
- MIN("-",1) { @Override protected double calc(double a, double b) { return a - b; } },
94
+ static Operator MIN = new Operator("-",1) { @Override protected double calc(double a, double b) { return a - b; } };
95
- MUL("*",2) { @Override protected double calc(double a, double b) { return a * b; } },
95
+ static Operator MUL = new Operator("*",2) { @Override protected double calc(double a, double b) { return a * b; } };
96
- DIV("/",2) { @Override protected double calc(double a, double b) { return a / b; } },
96
+ static Operator DIV = new Operator("/",2) { @Override protected double calc(double a, double b) { return a / b; } };
97
- BS("(",0),
97
+ static Operator BS = new Operator("(",0);
98
- BE(")",0);
98
+ static Operator BE = new Operator(")",0);
99
+
100
+ private static Operator[] values = { PLS, MIN, MUL, DIV, BS, BE };
99
101
 
100
102
  private final String text;
101
103
  private final int pri;
102
- Operator(String text, int pri) {
104
+ private Operator(String text, int pri) {
103
105
  this.text = text;
104
106
  this.pri = pri;
105
107
  }
106
108
 
107
109
  static Operator of(char c) {
108
- for(Operator ope : values()) if(ope.text.charAt(0) == c) return ope;
110
+ for(Operator ope : values) if(ope.text.charAt(0) == c) return ope;
109
111
  return null;
110
112
  }
111
113
 
@@ -179,8 +181,8 @@
179
181
  }
180
182
  }
181
183
 
182
- private enum Mode {
184
+ private static class Mode {
183
- NUM {
185
+ static Mode NUM = new Mode() {
184
186
  Mode translate(Source src, Destination dst) {
185
187
  if(src.getChar() == '(') {
186
188
  dst.put(src.nextOperator());
@@ -189,8 +191,8 @@
189
191
  dst.put(src.nextNumber());
190
192
  return OP;
191
193
  }
192
- },
194
+ };
193
- OP {
195
+ static Mode OP = new Mode() {
194
196
  Mode translate(Source src, Destination dst) {
195
197
  Operator op = src.nextOperator();
196
198
  if(op == Operator.BE) {
@@ -203,7 +205,8 @@
203
205
  }
204
206
  };
205
207
 
208
+ private Mode() {}
206
- abstract Mode translate(Source src, Destination dst);
209
+ Mode translate(Source src, Destination dst) { return null; };
207
210
  }
208
211
 
209
212
  static List<Element> translate(String formula) {

4

コードコメント修正

2023/02/11 04:04

投稿

jimbe
jimbe

スコア12659

test CHANGED
@@ -46,13 +46,13 @@
46
46
 
47
47
  class Stack<T> {
48
48
  private List<T> list = new List<>();
49
- /** 先頭に追加
49
+ /** トップに追加
50
50
  * @param v 追加するデータ */
51
51
  void push(T v) { list.add(v); }
52
- /** 先頭から取り出し
52
+ /** トップから取り出し
53
53
  * @return データ */
54
54
  T pop() { return list.remove(list.size()-1); }
55
- /** 先頭を確認
55
+ /** トップを確認
56
56
  * @return データ */
57
57
  T peek() { return list.get(list.size()-1); }
58
58
  /** 空判定

3

コード修正

2023/02/11 04:02

投稿

jimbe
jimbe

スコア12659

test CHANGED
@@ -2,29 +2,38 @@
2
2
  簡単になったとは思えませんが…。
3
3
  ```java
4
4
  class List<T> {
5
- private Object[] values;
5
+ private Object[] values = new Object[0];
6
- private int cap = 0, size = 0;
6
+ private int size = 0;
7
7
  List() {}
8
8
  List(List<T> org) {
9
- cap = org.cap;
10
9
  size = org.size;
11
- values = new Object[cap];
10
+ values = new Object[org.values.length];
12
11
  for(int i=0; i<size; i++) values[i] = org.values[i];
13
12
  }
13
+ /** 最後に追加
14
+ * @param v 追加するデータ */
14
15
  void add(T v) {
15
- if(size == cap) {
16
+ if(size == values.length) {
16
- Object[] newValues = new Object[cap+=10];
17
+ Object[] newValues = new Object[values.length + 10];
17
18
  for(int i=0; i<size; i++) newValues[i] = values[i];
18
19
  values = newValues;
19
20
  }
20
21
  values[size++] = v;
21
22
  }
23
+ /** i 番目を削除
24
+ * @param i インデックス(0 ～ size()-1)
25
+ * @return 削除したデータ */
22
26
  T remove(int i) {
23
27
  T v = (T)values[i];
24
28
  for(size--; i<size; i++) values[i] = values[i+1];
25
29
  return v;
26
30
  }
31
+ /** i 番目を取得
32
+ * @param i インデックス(0 ～ size()-1)
33
+ * @return データ */
27
34
  T get(int i) { return (T)values[i]; }
35
+ /** 件数
36
+ * @return 件数 */
28
37
  int size() { return size; }
29
38
  @Override
30
39
  public String toString() {
@@ -37,9 +46,17 @@
37
46
 
38
47
  class Stack<T> {
39
48
  private List<T> list = new List<>();
49
+ /** 先頭に追加
50
+ * @param v 追加するデータ */
40
51
  void push(T v) { list.add(v); }
52
+ /** 先頭から取り出し
53
+ * @return データ */
41
54
  T pop() { return list.remove(list.size()-1); }
55
+ /** 先頭を確認
56
+ * @return データ */
42
57
  T peek() { return list.get(list.size()-1); }
58
+ /** 空判定
59
+ * @return 空なら true */
43
60
  boolean isEmpty() { return list.size() == 0; }
44
61
  }
45
62
 

2

結果追加

2023/02/10 19:04

投稿

jimbe
jimbe

スコア12659

test CHANGED
@@ -219,3 +219,10 @@
219
219
  }
220
220
  }
221
221
  ```
222
+ ```
223
+ 1+2.5*-3=[1, 2.5, -3, *, +]=-6.5
224
+ 100*50/20=[100, 50, *, 20, /]=250.0
225
+ (20+30)*5=[20, 30, +, 5, *]=250.0
226
+ 2(3+5)/4=[2, 3, 5, +, *, 4, /]=4.0
227
+ 1+(2(3+((5/2)-2)))=[1, 2, 3, 5, 2, /, 2, -, +, *, +]=8.0
228
+ ```

1

説明修正

2023/02/10 19:01

投稿

jimbe
jimbe

スコア12659

test CHANGED
@@ -1,4 +1,4 @@
1
- リスト、スタックを配列で定義し、正規表現をコード化しました。
1
+ リストを配列で定義し、スタックはそのリストを利用するように定義、正規表現をコード化しました。
2
2
  簡単になったとは思えませんが…。
3
3
  ```java
4
4
  class List<T> {