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