中序轉後序
把中序存成list
(53+(34 * 45))
把中序運算式轉成list，要考慮十位、百位以上的數字，例:53,100
如果字母介於0 - 9，使用while把十位與個位拚接在temp變數中。
1
2
3
4
5
6
String temp = "";
while (i < str.length() &&
str.charAt(i) >= '0' && str.charAt(i) <= '9') {
temp += str.charAt(i);
i++;
}
中序轉後序步驟
判斷數字與左右括號
準備二個容器，一個是Stack，一個是List。
Stack是放「加減乘除」與左括號(，List是放數字
數字
數字直接加入list，記得正規式後面要有+加號，\\d+代表不只一個數字，而是由1至多個數字組成。
1
2
3
if (str.matches("\\d+")) {
list.add(str);
}
左括號
Stack是放「加減乘除」與左括號(。
把左括號加入stack。
1
2
3
if (str.equals("(")) {
stack1.add(str);
}
右括號
peek是檢查堆疊頂端元素，並非pop刪除元素。
1
stack1.peek()
把「加減乘除」符號放入List中，直到遇見右括號)停止。
1
2
3
while (!stack1.peek().equals("(")) {
list.add(stack1.pop());
}
最後要把右括號)，pop出去。
stack1.pop();
加減乘除判斷優先順序
數字愈大代表優先等級愈高，乘與除的的優先順序最高，要注意的是，左括號(仍在stack中，所以遇到左括號要傳回0。
1
2
3
4
5
6
7
8
9
public static int piorty(String str) {
if (str.equals("+") || str.equals("-")) {
return 1;
} else if (str.equals("*") || str.equals("/")) {
return 2;
} else { // 左括號
return 0;
}
}
如果str是「加減乘除」其中之一，判斷優先次序，優先次序低的，先把stack中比它大的都pop出來放入List，最後再把str(加減乘除其中之一)，放入stack中。
1
2
3
4
5
6
7
// 優先次序低的，先把stack中比str大的都pop出來放入List
while (stack1.size() != 0 &&
piorty(str) < piorty(stack1.peek())) {
list.add(stack1.pop());
}
// 最後再把str(加減乘除其中之一)，放入stack中
stack1.add(str);
計算
之前的步驟，會建立後序的數字與符號，把它遍歷一遍。
建立一個Stack。
計算步驟
數字
若為數字，就放入Stack。
1
2
3
if (str.matches("\\d+")) {
stack.add(str);
}
Stack前2個數字
若是加減乘除，把Stack前2個數字拿出來。
遇到減號，stack[top - 1] - stack[top]。
top頂端的後面一位的數 - top頂端。
1
2
3
4
// pop出頂端
int i2 = Integer.parseInt(stack.pop());
// pop出頂端的下一個
int i1 = Integer.parseInt(stack.pop());
加減乘除
判斷加減乘除
1
2
3
4
5
6
7
8
9
10
int result = 0;
if (str.equals("+")) {
result = i1 + i2;
} else if (str.equals("-")) {
result = i1 - i2;
} else if (str.equals("*")) {
result = i1 * i2;
} else if (str.equals("/")) {
result = i1 / i2;
}
計算結果放回Stack
1
stack.add(result + "");
完整程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
public class InfixToPostfix {
public static void main(String[] args) {
String infix = "(53+(34 * 45))";
List<String> infixList = parseInfix(infix);
System.out.println(infixList);
Stack<String> stack1 = new Stack<>();
List<String> list = new ArrayList<>();
for (String str: infixList) {
if (str.matches("\\d+")) {
list.add(str);
} else if (str.equals("(")) {
stack1.add(str);
} else if (str.equals(")")) {
while (!stack1.peek().equals("(")) {
list.add(stack1.pop());
}
stack1.pop();
} else {
while (stack1.size() != 0 && piorty(str) < piorty(stack1.peek())) {
list.add(stack1.pop());
}
stack1.add(str);
}
}
while (stack1.size() != 0) {
list.add(stack1.pop());
}
System.out.println(list);
int calculate = calculate(list);
System.out.println(calculate);
}
public static List parseInfix(String str) {
List<String> rtn = new ArrayList<>();
int i = 0;
while (i < str.length()) {
if (str.charAt(i) < '0' || str.charAt(i) > '9') {
rtn.add(str.charAt(i) + "");
i++;
} else {
String temp = "";
while (i < str.length() && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
temp += str.charAt(i);
i++;
}
rtn.add(temp);
}
}
return rtn;
}
public static int piorty(String str) {
if (str.equals("+") || str.equals("-")) {
return 1;
} else if (str.equals("*") || str.equals("/")) {
return 2;
} else {
return 0;
}
}
public static int calculate(List<String> list) {
Stack<String> stack = new Stack<>();
for (String str: list) {
if (str.matches("\\d+")) {
stack.add(str);
} else {
int i2 = Integer.parseInt(stack.pop());
int i1 = Integer.parseInt(stack.pop());
int result = 0;
if (str.equals("+")) {
result = i1 + i2;
} else if (str.equals("-")) {
result = i1 - i2;
} else if (str.equals("*")) {
result = i1 * i2;
} else if (str.equals("/")) {
result = i1 / i2;
}
stack.add(result + "");
}
}
return Integer.parseInt(stack.pop());
}
}
[(, 53, +, (, 34, *, 45, ), )]
[53, 34, 45, *, +]
1583