1.概念解析
实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中序表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。
2.实现算法
1.算法一
- 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
- 从左至右扫描中缀表达式；
- 遇到操作数时，将其压s2；
- 遇到运算符时，比较其与s1栈顶运算符的优先级：
- 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
- 否则，若优先级比栈顶运算符的高，也将运算符压入s1；
- 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
- 遇到括号时： (1) 如果是左括号“(”，则直接压入s1 (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
- 重复步骤2至5，直到表达式的最右边
- 将s1中剩余的运算符依次弹出并压入s2
- 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
2.算法2
将一个普通的中序表达式转换为逆波兰表达式的一般算法是：
首先需要分配2个栈，一个作为临时存储运算符的栈S1（含一个结束符号），一个作为输入逆波兰式的栈S2（空栈），S1栈可先放入优先级最低的运算符#，注意，中缀式应以此最低优先级的运算符结束。可指定其他字符，不一定非#不可。从中缀式的左端开始取字符，逐序进行如下步骤：
（1）若取出的字符是操作数，则分析出完整的运算数，该操作数直接送入S2栈
（2）若取出的字符是运算符，则将该运算符与S1栈栈顶元素比较，如果该运算符优先级(不包括括号运算符)大于S1栈栈顶运算符优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送入S2栈中，直至S1栈栈顶运算符低于（不包括等于）该运算符优先级，最后将该运算符送入S1栈。
（3）若取出的字符是“（”，则直接送入S1栈顶。
（4）若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个出栈，依次送入S2栈，此时抛弃“（”。
（5）重复上面的1~4步，直至处理完所有的输入字符
（6）若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送入S2栈。
完成以上步骤，S2栈便为逆波兰式输出结果。不过S2应做一下逆序处理。便可以按照逆波兰式的计算方法计算了！
3.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
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
| package DataStructures.Stack;
import java.util.Stack;
public class PolandNotaion {
public static void main(String[] args) {
Stack<String> operatStack = new Stack();
Stack<String> polanStack = new Stack();
String expersstion = "1 + ( ( 2 + 3 ) * 4 ) - 5";
String[] arrayStr = expersstion.split(" ");
int size = arrayStr.length;
System.out.println(size);
boolean flag = true;
for (int index = 0; index < size; index++) {
String str = arrayStr[index];
if (isNum(str)) {
polanStack.push(str);
} else {
if (operatorLevel(str) == 1) {
if (str.equals("(")) {
operatStack.push(str);
} else {
boolean f1 = true;
while (f1) {
String s = operatStack.peek();
if (s.equals("(")) {
operatStack.pop();
f1 = false;
} else {
polanStack.push(operatStack.pop());
}
}
}
} else {
flag = true;
while (flag) {
if (operatStack.size() == 0 || operatStack.peek().equals("(")) {
operatStack.push(str);
flag = false;
} else {
int L1 = operatorLevel(str);
int L2 = operatorLevel(operatStack.peek());
if (L1 < L2) {
operatStack.push(str);
System.out.println("L!");
flag = false;
} else {
polanStack.push(operatStack.pop());
}
}
}
}
}
}
while (operatStack.size() != 0) {
polanStack.push(operatStack.pop());
}
System.out.println(polanStack);
}
static public boolean isNum(String string) {
if (operatorLevel(string) > 4) {
int num = Integer.parseInt(string);
if (num <= 9 || num >= 0) {
return true;
}
}
return false;
}
static public int operatorLevel(String string) {
switch (string) {
case "(":
return 1;
case ")":
return 1;
case "+":
return 3;
case "-":
return 3;
case "*":
return 2;
case "/":
return 2;
case "#":
return 4;
default:
return 5;
}
}
}
|
