后缀表达式
概念与表示
对表达式的记法
前缀表达式、中缀表达式、后缀表达式（逆波兰式）它们都是对表达式的记法。它们之间的区别在于运算符相对与操作数的位置不同：前缀表达式的运算符位于与其相关的操作数之前；中缀和后缀同理。后缀表达式又称逆波兰式是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式形式，不需要括号来标识操作符的优先级。
举例：
(3 + 4) × 5 - 6 就是中缀表达式
- × + 3 4 5 6 前缀表达式
3 4 + 5 × 6 - 后缀表达式
为何使用后缀表达式？
中缀表达式是人们常用的算术表示方法。虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。
中缀到后缀的表示
转化规则
需要分配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应做一下逆序处理。便可以按照逆波兰式的计算方法计算
举例：
代码
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
152
153
154
155
| public class MyCharStack {
private char[] array;
private int maxSize;
private int top;
public MyCharStack(int size){
this.maxSize = size;
array = new char[size];
top = -1;
}
public void push(char value){
if(top < maxSize-1){
array[++top] = value;
}
}
public char pop(){
return array[top--];
}
public char peek(){
return array[top];
}
public char peekN(int n){
return array[n];
}
public void displayStack(){
System.out.print("Stack(bottom-->top):");
for(int i = 0 ; i < top+1; i++){
System.out.print(peekN(i));
System.out.print(' ');
}
System.out.println("");
}
public String StackToString(){
StringBuilder str = new StringBuilder();
for(int i = 0 ; i < top+1; i++){
str.append(peekN(i));
}
return String.valueOf(str);
}
public boolean isEmpty(){
return (top == -1);
}
public boolean isFull(){
return (top == maxSize-1);
}
}
public class InfixToSuffix {
private MyCharStack s1;
private MyCharStack s2;
private String input;
public InfixToSuffix(String in) {
input = in;
s1 = new MyCharStack(input.length());
s2 = new MyCharStack(input.length());
}
public MyCharStack doTrans() {
for (int j = 0; j < input.length(); j++) {
char ch = input.charAt(j);
switch (ch) {
case '+':
case '-':
gotOper(ch, 1);
break;
case '×':
case '÷':
gotOper(ch, 2);
break;
case '(':
s1.push(ch);
break;
case ')':
gotParen(ch);
break;
default:
s2.push(ch);
break;
}
}
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
return s2;
}
、
public void gotOper(char opThis, int prec1) {
while (!s1.isEmpty()) {
char opTop = s1.pop();
if (opTop == '(') {
s1.push(opTop);
break;
} else {
int prec2;
if (opTop == '+' || opTop == '-') {
prec2 = 1;
} else {
prec2 = 2
}
if (prec2 < prec1) {
s1.push(opTop);
break;
} else {
s2.push(opTop);
}
}
}
s1.push(opThis);
}
public void gotParen(char ch) {
while (!s1.isEmpty()) {
char chx = s1.pop();
if (chx == '(') {
break;
} else {
s2.push(chx);
}
}
}
}
|
后缀表达式的计算
新建一个表达式,如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。
代码
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
| public class PostFix {
public double evalPostFix(String token) {
Stack<Double> s = new Stack<Double>();
double a, b, result = 0.0;
boolean isNumber;
for (int i = 0; i < token.length() - 1; i++) {
try {
isNumber = true;
result = Double.parseDouble(token);
} catch (Exception e) {
isNumber = false;
}
if (isNumber)
s.push(result);
else
{
switch (token.charAt(0)) {
case '+':
a = s.pop();
b = s.pop();
s.push(b + a);
break;
case '-':
a = s.pop();
b = s.pop();
s.push(b - a);
break;
case '÷':
a = s.pop();
b = s.pop();
s.push(b / a);
break;
case '×':
a = s.pop();
b = s.pop();
s.push(b * a);
break;
}
}
}
return s.peek();
}
public int calculate(String is) {
String[] s = is.split("");
ArrayList<String> list = new ArrayList<>();
Collections.addAll(list, s);
Stack<String> stack = new Stack<>();
for (String item : list) {
if (item.matches("\\d+")) {
stack.push(item);
} else {
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if (item.equals("+")) {
res = num1 + num2;
} else if (item.equals("-")) {
res = num1 - num2;
} else if (item.equals("×")) {
res = num1 * num2;
} else if (item.equals("÷")) {
res = num1 / num2;
}
stack.push("" + res);
}
}
return Integer.parseInt(stack.pop());
}
}
|
