1、使用调度场算法(Shunting Yard Algorithm)实现用逆波兰表示法(后缀表示法)表示中缀表达式

算法的详细描述:
  • 当还有记号可以读取时:
    • 读取一个记号。
    • 如果这个记号表示一个数字,那么将其添加到输出队列中。
    • 如果这个记号表示一个操作符,记做o1,那么:
      • 只要存在另一个记为o2的操作符位于栈的顶端,并且如果o1的运算符优先级要小于或者等于o2的优先级,那么将o2从栈的顶端弹出并且放入输出队列中(循环直至以上条件不满足为止);
      • 然后,将o1压入栈的顶端。
    • 如果这个记号是一个左括号,那么就将其压入栈当中。
    • 如果这个记号是一个右括号,那么:
      • 从栈当中不断地弹出操作符并且放入输出队列中,直到栈顶部的元素为左括号为止。
      • 将左括号从栈的顶端弹出,但并不放入输出队列中去。
  • 当再没有记号可以读取时:
    • 如果此时在栈当中还有操作符,将操作符逐个弹出并放入输出队列中。
  • 退出算法。
算法的Java实现:
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
public String ShuntingYardAlgorithm(String expression){
//使用StringBuilder构建字符串生成器
StringBuilder notation = new StringBuilder(expression.length());
Stack<Character> stack = new Stack<Character>();
char[] array = expression.toCharArray();
for(char element: array){
//记号表示一个数字
if('0' <= element && element <= '9')
notation.append(element);
//记号表示一个操作符
else if("+-*/".indexOf(element) >= 0){
if(!stack.empty()){
while(!isPrior(element, stack.peek())){
notation.append(stack.peek());
stack.pop();
if(stack.empty())
break;
}
}
stack.push(element);
}
//记号表示一个左括号
else if(element == '(')
stack.push(element);
//记号表示一个右括号
else if(element == ')'){
if(!stack.empty()){
while(stack.peek() != '('){
notation.append(stack.peek());
stack.pop();
if(stack.empty())
break;
}
}
if(!stack.empty())
stack.pop();
}
}//读取记号结束
//弹出堆栈中的剩余元素
while(!stack.empty()){
notation.append(stack.peek());
stack.pop();
}
//由字符串生成器返回一个字符串对象
return notation.toString();
}
//操作符及括号的优先级,数字越小,优先级越高
public int priorityOf(char operator){
int priority = 0;
switch(operator){
case '(': priority = 4;break;
case ')': priority = 4;break;
case '+': priority = 3;break;
case '-': priority = 3;break;
case '*': priority = 2;break;
case '/': priority = 2;break;
}
return priority;
}
//记号表示一个操作符比较优先级
//前者优先级低于后者时返回true
public boolean isPrior(char operator1, char operator2){
return priorityOf(operator1) < priorityOf(operator2);
}

需要注意的是,在取栈顶元素peek()和删除栈顶元素pop()时,要判断当前堆栈是否为空,否则会出现java.util.EmptyStackException

2、由逆波兰表达式得到结果

算法的详细描述:
  • 当还有记号可以读取时:
    • 读取一个记号。
    • 如果这个记号表示一个数字,那么将其压入栈当中。
    • 如果这个记号表示一个操作符,那么:
      • 从栈中弹出两个数字,进行对应的算术运算。
      • 将运算结果压入栈当中。
  • 当再没有记号可以读取时:
    • 将栈顶元素弹出作为结果。
  • 退出算法。
算法的Java实现:
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
public int SolveReversePolishNotation(String notation){
//定义value为结果
int value = 0;
Stack<Integer> stack = new Stack<Integer>();
char[] array = notation.toCharArray();
for(char element: array){
//记号表示一个数字
if('0' <= element && element <= '9')
stack.push(element - '0');
//记号表示一个运算符
else if("+-*/".indexOf(element) >= 0){
int top = 0, next = 0;
if(!stack.empty()){
top = stack.peek();
stack.pop();
}
if(!stack.empty()){
next = stack.peek();
stack.pop();
}
//进行与运算符对应的运算
switch(element){
case '+': top = next + top;break;
case '-': top = next - top;break;
case '*': top = next * top;break;
case '/': top = next / top;break;
}
stack.push(top);
}
}
//弹出栈顶元素作为结果
if(!stack.empty())
value = stack.peek();
return value;
}

一个简单的测试程序:

1
2
3
4
5
6
7
8
9
10
11
import java.util.*;
public class Test{
public static void main(String[] args){
String expression = "7+(8-9)*2";
String notation = ShuntingYardAlgorithm(expression);
System.out.println("notation: " + notation);
int result = SolveReversePolishNotation(notation);
System.out.println("result: " + result);
}
}
输出结果为:
1
2
notation: 789-2*+
result: 5

参考文档:

逆波兰表示法-维基百科

调度场算法-维基百科

LeetCode-Evaluate Reverse Polish Notation