中缀表达式转后缀表达式(逆波兰)

一、中缀表达式转后缀表达式

中缀表达式就是普通的表达式。如:9+(3-1)*3+10/2
后缀表达式是一种不需要括号的表示法,又叫逆波兰表达式。

上面的式子用后缀法表示:9 3 1 - 3 * + 10 2 / +

那么如何转化成后缀表达式?

思路:

从左往右遍历:
1. 如果是数字则直接输出
2. 如果是符号则入栈,但要通过以下判断

  • 若该符号c是右括号或者c的优先级≤栈顶符号,则栈中元素依次出栈输出,c入栈

代码实现:

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
//中缀转后缀表达式(逆波兰)------栈实现
public class NiPoLan2 {
public static void main(String[] args) {
//创建栈
Stack<String> s = new Stack<String>();
String s1 = "9+(3-1)*3+10/2"; //例子 (1-2)*(4+5) 9+(3-1)*3+10/2
char[] o = s1.toCharArray();
String r = ""; //字符串r记录输出
//遍历
for(int i=0;i<o.length;i++){
//符号是数字
if(Character.isDigit(o[i])){
//判断两位整数,如10
if(i<o.length-1&&Character.isDigit(o[i+1])){
r = r+o[i]+o[i+1]+" ";
i++; //减少一次循环
continue;
}
r = r+o[i]+" ";
}
//符号是 (
if(o[i]=='('){
s.push(o[i]+"");
}
//符号是+ or -
if(o[i]=='+'|o[i]=='-'){
//栈不为空,且有乘除符号,则弹出
if(!s.isEmpty()&&(s.peek().equals("*")|s.peek().equals("/"))){
//全部出栈
while(!s.isEmpty()){
r = r + s.pop()+" ";
}
//出栈后,再将+-入栈
s.push(o[i]+"");
//栈为空
}else{
s.push(o[i]+"");
System.out.println(o[i]+"");
}
}
//符号是右括号则配对
if(o[i]==')'){
String a = s.pop();
System.out.println(a);
r = r + a+" ";
s.pop();
}
//符号是乘除
if(o[i]=='*'|o[i]=='/'){
System.out.println(s.peek());
//栈顶是加减、括号
if(s.isEmpty()){
s.push(o[i]+"");
}else if(s.peek().equals("+")|s.peek().equals("-")|s.peek().equals("(")){ //s.peek()=="-"|s.peek()=="+"|s.peek()=="("
s.push(o[i]+"");
}
//栈顶是乘除,则出栈
else if(s.peek()=="*"|s.peek()=="/"){
//全部出栈
while(!s.isEmpty()){
r = r + s.pop();
}
s.push(o[i]+"");
}
}
}
//最后栈中不为空,全部出栈
while(!s.isEmpty()){
r = r + s.pop()+" ";
}
System.out.println(r);
}
}

输出结果:

1
9 3 1 - 3 * + 10 2 / +

二、计算后缀表达式

中缀表达式容易计算:9+(3-1)*3+10/2=20
那么后缀表达式如何计算呢?

还是上面的例子: 9 3 1 - 3 * + 10 2 / +

思路:

从左往右遍历:

  1. 遇到数字就入栈
  2. 遇到符号就将栈顶的两个元素取出计算,将结果入栈;最后栈中的数就是最终结果

代码实现:

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
public class NiPoLan {
public static void main(String[] args) {
Stack<Integer> s = new Stack<Integer>();
String s1 = "9 3 1 - 3 * + 10 2 / +";
String[] r = s1.split(" "); //转为字符串数组
System.out.println(s1);
for(int i=0;i<r.length;i++){
//判断字符串r[i]是数字还是符号
//r[i]是数字,入栈
if(Character.isDigit(r[i].charAt(0))){
int c = Integer.valueOf(r[i]);
s.push(c);
}else{
//r[i]是符号,则运算
switch (r[i]) {
case "-":
int a = s.pop();
int 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;
default:
break;
}
}
}
//输出结果
System.out.println(s.pop());
}
}

输出结果:

1
2
9 3 1 - 3 * + 10 2 / +
20

结果为 20。