逆波兰算法
1后缀表达式
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素
和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下**:**
1)从左至右扫描，将3和4压入堆栈；
2)遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
3)将5入栈；
4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
5)将6入栈；
6)最后是-运算符，计算出35-6的值，即29，由此得出最终结果
按照操作顺序来计算（所读取的是数字就加入，是符号就弹出，并进行求和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| String string="30 4 + 5 * 6 -";
String[] strings=s2.split(" ");
Stack<Integer> stack=new Stack<>();
for (int i = 0; i < strings.length; i++) {
String s = strings[i];
if (s.matches("\\d+")){
stack.push(Integer.parseInt(s));
}else {
int num1=stack.pop();
int num2=stack.pop();
int res=0;
if (s.equals("+")){
res=num1+num2;
}else if(s.equals("-")){
res=num2-num1;
}else if(s.equals("*")){
res=num1*num2;
}else {
res=num2/num1;
}
stack.push(res);
}
}
|
2中缀转后缀的原理
1)初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2)从左至右扫描中缀表达式；
3)遇到操作数时，将其压s2；
4)遇到运算符时，比较其与s1栈顶运算符的优先级：
(1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
(2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；
(3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
5)遇到括号时：
(1) 如果是左括号“(”，则直接压入s1
(2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6)重复步骤2至5，直到表达式的最右边
7)将s1中剩余的运算符依次弹出并压入s2
8)依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达****式
一个栈，一个list，栈收集符号，list收集数字最初，档位空或者“（”直接加入栈，优先级高也是直接加入，直到是优先级比较低的，那就直接把栈顶弹出去给加到list里，再用操作符与弹出后的比优先级，如果是“）”，也是弹到list，直到操作符为“（”，弹出这个操作符“（”，然后进行下一趟，操作代码
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
| public static List<String> produce(List<String> list){
Stack<String> stack1=new Stack<>();
List<String> list1=new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
String s1=list.get(i);
if (s1.matches("\\d+")){
list1.add(s1);
}else{
if (stack1.isEmpty()){
stack1.push(s1);
}else if (s1.equals("(")){
stack1.push(s1);
}else if (s1.equals(")")){
while (!stack1.peek().equals("(")){
list1.add(stack1.pop());
}
stack1.pop();
}else if (priority(s1)<=priority(stack1.peek())){
while (!stack1.isEmpty()&&priority(s1)<=priority(stack1.peek())){
list1.add(stack1.pop());
}
stack1.push(s1);
}else {
stack1.push(s1);
}
}
}
while (!stack1.isEmpty()){
list1.add(stack1.pop());
}
return list1;
}
|
3完整的代码
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
| import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class 逆波兰 {
public static void main(String[] args) {
String s1="1+((2+3)*4)-5";
List<String> list=list(s1);
List<String> list1=produce(list);
String s2="";
for (int i = 0; i < list1.size(); i++) {
if (i!=list1.size()-1){
s2+=list1.get(i)+" ";
}else {
s2+=list1.get(i);
}
}
System.out.println(s2);
String string="30 4 + 5 * 6 -";
String[] strings=s2.split(" ");
Stack<Integer> stack=new Stack<>();
for (int i = 0; i < strings.length; i++) {
String s = strings[i];
if (s.matches("\\d+")){
stack.push(Integer.parseInt(s));
}else {
int num1=stack.pop();
int num2=stack.pop();
int res=0;
if (s.equals("+")){
res=num1+num2;
}else if(s.equals("-")){
res=num2-num1;
}else if(s.equals("*")){
res=num1*num2;
}else {
res=num2/num1;
}
stack.push(res);
}
}
System.out.println(stack.peek());
}
public static int priority(String val){
if (val.equals("+")||val.equals("-")){
return 0;
}else if (val.equals("*")||val.equals("/")){
return 1;
}else {
return -1;
}
}
public static List<String> list(String string){
List<String> list = new ArrayList<>();
for (int i = 0; i < string.length(); i++) {
char ch=string.charAt(i);
if (ch>='0'&&ch<='9'){
String addn="";
addn+=ch;
for (int j = i+1; j < string.length(); j++) {
char ch2=string.charAt(j);
if (ch2>='0'&&ch2<='9'){
addn+=ch2;
}else {
i=j-1;
break;
}
}
list.add(addn);
}else {
list.add(""+ch);
}
}
return list;
}
public static List<String> produce(List<String> list){
Stack<String> stack1=new Stack<>();
List<String> list1=new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
String s1=list.get(i);
if (s1.matches("\\d+")){
list1.add(s1);
}else{
if (stack1.isEmpty()){
stack1.push(s1);
}else if (s1.equals("(")){
stack1.push(s1);
}else if (s1.equals(")")){
while (!stack1.peek().equals("(")){
list1.add(stack1.pop());
}
stack1.pop();
}else if (priority(s1)<=priority(stack1.peek())){
while (!stack1.isEmpty()&&priority(s1)<=priority(stack1.peek())){
list1.add(stack1.pop());
}
stack1.push(s1);
}else {
stack1.push(s1);
}
}
}
while (!stack1.isEmpty()){
list1.add(stack1.pop());
}
return list1;
}
}
|
