逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
中缀表达式和后缀表达式
将字符串表达式放入数组
将字符串表达式拆分成数组
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
| public String[] notationStrToArray(String notationStr) {
List<String> list = new ArrayList();
notationStr = notationStr.replaceAll(" ", "");
char[] chars = notationStr.toCharArray();
int keepNum = 0;
int preflag = 0;
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (preflag == 0 && c == 45) {
System.out.println("负数");
keepNum++;
} else if (isSymbol(c) && c != 32) {
if (keepNum > 0) {
String trim = notationStr.substring(i - keepNum, i).trim();
if (!trim.isEmpty()) list.add(trim);
keepNum = 0;
}
preflag = 0;
list.add(c + "");
} else {
preflag = 1;
keepNum++;
}
}
if (keepNum > 0) {
list.add(notationStr.substring(notationStr.length() - keepNum, notationStr.length()).trim());
}
System.out.println(list);
return list.toArray(new String[list.size()]);
}
|
中缀表达式转后缀表达式（逆波兰表达式）
将普通平常使用的中缀表达式转成后缀表达式（逆波兰表达式）。
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
| public String[] convertInfixToSuffix(String infixNotation) {
String[] strings = notationStrToArray(infixNotation);
Stack<String> symbolStack = new Stack<String>();
List<String> list = new ArrayList();
for (String str : strings) {
if (str.matches("^-?\\d+$")) {
list.add(str);
} else if (str.equals("(")) {
symbolStack.push(str);
} else if (str.equals(")")) {
while (!symbolStack.peek().equals("(")) {
list.add(symbolStack.pop());
}
symbolStack.pop();
} else {
while (!symbolStack.isEmpty()) {
String peek = symbolStack.peek();
if ("(".equals(peek)) {
break;
} else if (comparPriority(str, peek) < 0) {
list.add(symbolStack.pop());
} else {
break;
}
}
symbolStack.push(str);
}
}
while (!symbolStack.isEmpty()) {
list.add(symbolStack.pop());
}
return list.toArray(new String[list.size()]);
}
|
比较运算符的优先级
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int comparPriority(String thissymbol, String othersymbol) {
int re = 0, thislevel = 0, otherlevel = 0;
if ("*".equals(thissymbol) || "/".equals(thissymbol)) {
thislevel = 1;
} else if ("+".equals(thissymbol) || "-".equals(thissymbol)) {
thislevel = 0;
} else {
throw new RuntimeException("运算符有误");
}
if ("*".equals(othersymbol) || "/".equals(othersymbol)) {
otherlevel = 1;
} else if ("+".equals(othersymbol) || "-".equals(othersymbol)) {
otherlevel = 0;
} else {
throw new RuntimeException("运算符有误");
}
return thislevel - otherlevel;
}
public boolean isSymbol(char val) {
return val == '+' || val == '-' || val == '*' || val == '/' || val == '(' || val == ')';
}
|
逆波兰表达式的运算
逆波兰表达式的运算
方法一
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
|
public int evalRPN(String[] tokens) {
Stack<Integer> resStack = new Stack<Integer>();
for (String token : tokens) {
if (token.matches("^-?\\d+$")) {
resStack.push(Integer.parseInt(token));
} else {
int ev2 = resStack.pop();
int ev1 = resStack.pop();
int evre = 0;
switch (token) {
case "+":
evre = ev1 + ev2;
break;
case "-":
evre = ev1 - ev2;
break;
case "*":
evre = ev1 * ev2;
break;
case "/":
evre = ev1 / ev2;
break;
default:
}
resStack.push(evre);
}
}
return resStack.pop();
}
|
方法二（方法一的优化，推荐）
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
| public int evalRPN1(String[] tokens) {
Stack<Integer> resStack = new Stack<Integer>();
for (String token : tokens) {
int ev1, ev2 = 0;
switch (token) {
case "+":
ev2 = resStack.pop();
ev1 = resStack.pop();
resStack.push(ev1 + ev2);
break;
case "-":
ev2 = resStack.pop();
ev1 = resStack.pop();
resStack.push(ev1 - ev2);
break;
case "*":
ev2 = resStack.pop();
ev1 = resStack.pop();
resStack.push(ev1 * ev2);
break;
case "/":
ev2 = resStack.pop();
ev1 = resStack.pop();
resStack.push(ev1 / ev2);
break;
default:
resStack.push(Integer.parseInt(token));
break;
}
}
return resStack.pop();
}
|
方法三（推荐,使用数组模拟栈，可以节省内存）
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
| public int evalRPNArray(String[] tokens) {
int[] numStack = new int[tokens.length / 2 + 1];
int index = 0;
for (String s : tokens) {
switch (s) {
case "+":
numStack[index - 2] += numStack[--index];
break;
case "-":
numStack[index - 2] -= numStack[--index];
break;
case "*":
numStack[index - 2] *= numStack[--index];
break;
case "/":
numStack[index - 2] /= numStack[--index];
break;
default:
numStack[index++] = Integer.parseInt(s);
break;
}
}
return numStack[0];
}
|
完整代码：Github
