java.util.stack，繼承自Vector
FILO, 適合帶有小括號的算術運算
|
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
import java.util.Stack; /** * 利用棧，進行四則運算的類 * 用兩個棧來實現算符優先，一個棧用來保存需要計算的數據numStack,一個用來保存計算優先符priStack * * 基本算法實現思路為：用當前取得的運算符與priStack棧頂運算符比較優先級：若高于，則因為會先運算，放入棧頂； * 若等于，因為出現在后面，所以會后計算，所以棧頂元素出棧，取出操作數運算； * 若小于，則同理，取出棧頂元素運算，將結果入操作數棧。各個優先級'(' > '*' = '/' > '+' = '-' > ')' * */ public class Operate { private Stack<Character> priStack = new Stack<Character>();// 操作符棧 private Stack<Integer> numStack = new Stack<Integer>();;// 操作數棧 /** * 傳入需要解析的字符串，返回計算結果(此處因為時間問題，省略合法性驗證) * @param str 需要進行技術的表達式 * @return 計算結果 */ public int caculate(String str) { // 1.判斷string當中有沒有非法字符 String temp;// 用來臨時存放讀取的字符 // 2.循環開始解析字符串，當字符串解析完，且符號棧為空時，則計算完成 StringBuffer tempNum = new StringBuffer();// 用來臨時存放數字字符串(當為多位數時) StringBuffer string = new StringBuffer().append(str);// 用來保存，提高效率 while (string.length() != 0) { temp = string.substring(0, 1); string.delete(0, 1); // 判斷temp，當temp為操作符時 if (!isNum(temp)) { // 1.此時的tempNum內即為需要操作的數，取出數，壓棧，并且清空tempNum if (!"".equals(tempNum.toString())) { // 當表達式的第一個符號為括號 int num = Integer.parseInt(tempNum.toString()); numStack.push(num); tempNum.delete(0, tempNum.length()); } // 用當前取得的運算符與棧頂運算符比較優先級：若高于，則因為會先運算，放入棧頂；若等于，因為出現在后面，所以會后計算，所以棧頂元素出棧，取出操作數運算； // 若小于，則同理，取出棧頂元素運算，將結果入操作數棧。 // 判斷當前運算符與棧頂元素優先級，取出元素，進行計算(因為優先級可能小于棧頂元素，還小于第二個元素等等，需要用循環判斷) while (!compare(temp.charAt(0)) && (!priStack.empty())) { int a = (int) numStack.pop();// 第二個運算數 int b = (int) numStack.pop();// 第一個運算數 char ope = priStack.pop(); int result = 0;// 運算結果 switch (ope) { // 如果是加號或者減號，則 case '+': result = b + a; // 將操作結果放入操作數棧 numStack.push(result); break; case '-': result = b - a; // 將操作結果放入操作數棧 numStack.push(result); break; case '*': result = b * a; // 將操作結果放入操作數棧 numStack.push(result); break; case '/': result = b / a;// 將操作結果放入操作數棧 numStack.push(result); break; } } // 判斷當前運算符與棧頂元素優先級， 如果高，或者低于平，計算完后，將當前操作符號，放入操作符棧 if (temp.charAt(0) != '#') { priStack.push(new Character(temp.charAt(0))); if (temp.charAt(0) == ')') {// 當棧頂為'('，而當前元素為')'時，則是括號內以算完，去掉括號 priStack.pop(); priStack.pop(); } } } else // 當為非操作符時（數字） tempNum = tempNum.append(temp);// 將讀到的這一位數接到以讀出的數后(當不是個位數的時候) } return numStack.pop(); } /** * 判斷傳入的字符是不是0-9的數字 * * @param str * 傳入的字符串 * @return */ private boolean isNum(String temp) { return temp.matches("[0-9]"); } /** * 比較當前操作符與棧頂元素操作符優先級，如果比棧頂元素優先級高，則返回true，否則返回false * * @param str 需要進行比較的字符 * @return 比較結果 true代表比棧頂元素優先級高，false代表比棧頂元素優先級低 */ private boolean compare(char str) { if (priStack.empty()) { // 當為空時，顯然 當前優先級最低，返回高 return true; } char last = (char) priStack.lastElement(); // 如果棧頂為'('顯然，優先級最低，')'不可能為棧頂。 if (last == '(') { return true; } switch (str) { case '#': return false;// 結束符 case '(': // '('優先級最高,顯然返回true return true; case ')': // ')'優先級最低， return false; case '*': { // '*/'優先級只比'+-'高 if (last == '+' || last == '-') return true; else return false; } case '/': { if (last == '+' || last == '-') return true; else return false; } // '+-'為最低，一直返回false case '+': return false; case '-': return false; } return true; } public static void main(String args[]) { Operate operate = new Operate(); int t = operate.caculate("(3+4*(4*10-10/2)#"); System.out.println(t); } } |
補充：java stack實現的中綴簡單四則運算表達式計算
我就廢話不多說了，大家還是直接看代碼吧~
|
1
2
3
4
5
6
7
8
|
public abstract class Stack<T> { public abstract boolean isEmpty(); public abstract boolean isFull(); public abstract T top(); public abstract boolean push(T x); public abstract T pop(); public abstract void clear();} |
|
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
|
public class SeqStack<T> extends Stack<T> { private Object[] elementData; private int maxTop; private int top; public SeqStack(int size) { this.maxTop = size - 1; elementData = new Object[size]; top = -1; } @Override public boolean isEmpty() { return top == -1; } @Override public boolean isFull() { return top == maxTop - 1; } @SuppressWarnings("unchecked") @Override public T top() { if (top == -1) { System.out.println("Empty"); return null; } return (T) elementData[top]; } @Override public boolean push(T x) { if (top == maxTop) { System.err.println("Full"); return false; } elementData[++top] = x; return true; } @SuppressWarnings("unchecked") @Override public T pop() { if (top == -1) { System.err.println("Empty"); return null; } T result = (T)elementData[top]; elementData[top] = null; //gc top--; return result; } @Override public void clear() { //let gc do its work for(int i = 0; i < top+1; i++) { elementData[i] = null; } top = -1; }} |
|
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
public class StackCalc { private SeqStack<Integer> stack; public StackCalc(int maxSize) { stack = new SeqStack<Integer>(maxSize); } private void pushOperand(Integer number) { stack.push(number); } private Number doOperate(char oper) { Integer right = stack.pop(); Integer left = stack.pop(); Integer result = null; if (left != null && right != null) { switch (oper) { case '+': result = left.intValue() + right.intValue(); break; case '-': result = left.intValue() - right.intValue(); break; case '*': result = left.intValue() * right.intValue(); break; case '/': if (right.intValue() == 0) { System.err.println("Divide by 0"); } result = left.intValue() / right.intValue(); break; default: break; } } stack.push(result); return result; } private int icp(char c) { switch (c) { case '#': return 0; case '(': return 7; case '*': return 4; case '/': return 4; case '+': return 2; case '-': return 2; case ')': return 1; default: return -1; } } private int isp(int c) { switch (c) { case '#': return 0; case '(': return 1; case '*': return 5; case '/': return 5; case '+': return 3; case '-': return 3; case ')': return 7; default: return -1; } } public String transfer(String expression) { StringBuilder sb = new StringBuilder(); SeqStack<Character> stack = new SeqStack<Character>(expression.length()); stack.push('#'); for (int i = 0; i < expression.length(); i++) { Character c = expression.charAt(i); if ('0' <= c && c <= '9' || 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z') { // digit character sb.append(c); } else { // 操作符 if (icp(c) > isp(stack.top())) { // 進棧 stack.push(c); } else { // 出棧 if (c == ')') { char ch = stack.pop(); while (ch != '(') { sb.append(ch); ch = stack.pop(); } } else { char ch = stack.pop(); while (icp(c) <= isp(ch)) { sb.append(ch); ch = stack.pop(); } stack.push(ch); stack.push(c); } } } } // end of for char ch = stack.pop(); while (ch != '#') { sb.append(ch); ch = stack.pop(); } stack.clear(); return sb.toString(); } public Integer calc(String expression) { expression = transfer(expression); for (int i = 0; i < expression.length(); i++) { char c = expression.charAt(i); switch (c) { case '+': case '-': case '*': case '/': doOperate(c); break; default: pushOperand(new Integer(c + "")); break; } } return stack.pop(); } /** * @param args */ public static void main(String[] args) { StackCalc calc = new StackCalc(10); System.out.println(calc.calc("6/(4-2)+3*2")); }} |
以上為個人經驗，希望能給大家一個參考，也希望大家多多支持服務器之家。如有錯誤或未考慮完全的地方，望不吝賜教。
原文鏈接：https://blog.csdn.net/kangbin825/article/details/71437086
