-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathInfixToPostfix
More file actions
148 lines (132 loc) · 5.14 KB
/
Copy pathInfixToPostfix
File metadata and controls
148 lines (132 loc) · 5.14 KB
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
package ChapterOne.Three;
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
import java.util.regex.Pattern;
/**
* 使用方法：与EvaluatePostfix一起使用，使用管道将该输出作为EvaluatePostfix的输入，计算算式结果
* java ChapterOne.Three.InfixToPostfix | java ChapterOne.Three.EvaluatePostfix
* 将中序转换为后序表达式
* 算法思路：
* 1.从左到右开始扫描中序表达式
* 2.遇到数字直接加入后序表达式
* 3. 遇到'('加入栈中，
* 4. 遇到')'将栈中运算符弹出，直到'('，将'('删除
* 5. 当前扫描的运算符优先级比除'('以外的栈顶元素优先级高，则入栈；低，则出栈，直到当前扫描运算符大于栈顶元素优先级，或遇到'('
*/
public class InfixToPostfix {
private static int priority(String op){
if(op.equals("*")||op.equals("/"))
return 1;
else if(op.equals("+")||op.equals("-"))
return 0;
return -1;
}
private static boolean isOperator(String op){
return op.equals("+")||op.equals("-")||op.equals("*")||op.equals("/");
}
private static boolean isNumber(String num){
Pattern pattern=Pattern.compile("[-]?[\\d]+");
return pattern.matcher(num).matches();
}
private static List<String> stringToList(String infix){
List<String> list=new ArrayList<>();
int index = 0;
do{
char ch = infix.charAt(index);
if(ch < 48 || ch > 57){
//是操作符，直接添加至list中
index ++ ;
list.add(ch+"");
}else {
//是数字,判断多位数的情况
StringBuilder sb=new StringBuilder();
while (index < infix.length() && infix.charAt(index) >=48 && infix.charAt(index) <= 57){
sb.append(infix.charAt(index));
index ++;
}
list.add(sb.toString());
}
}while (index < infix.length());
return list;
}
public List<String> transform(String expression){
List<String> infix=stringToList(expression);
Stack<String> stack=new Stack<>();
List<String> postfix=new ArrayList<>();//后序表达式
for(String i:infix){
if (isNumber(i)) postfix.add(i);
else if(i.equals("(")) stack.push(i);
else if(i.equals(")")) {
while(!stack.isEmpty()&&!stack.peek().equals("("))
postfix.add(stack.pop());
stack.pop();
} else if (isOperator(i)){//为运算符时
if(stack.isEmpty()||stack.peek().equals("(")||priority(i)>priority(stack.peek()))//优先级高，入栈
stack.push(i);
else{
while(!stack.isEmpty()&&!stack.peek().equals("(")&&priority(i)<=priority(stack.peek())){
postfix.add(stack.pop());
}
//当前操作符压栈
stack.push(i);
}
}else
throw new RuntimeException("有非法字符");
}
while (!stack.isEmpty())
postfix.add(stack.pop());
return postfix;
}
/**
* 与Evaluate_pipe配合使用
* @param expression
*/
public void transform_pipe(String expression){
List<String> infix=stringToList(expression);
Stack<String> stack=new Stack<>();
for(String i:infix){
if (isNumber(i)) System.out.println(i);
else if(i.equals("(")) stack.push(i);
else if(i.equals(")")) {
while(!stack.isEmpty()&&!stack.peek().equals("("))
System.out.println(stack.pop());
stack.pop();
} else if (isOperator(i)){//为运算符时
if(stack.isEmpty()||stack.peek().equals("(")||priority(i)>priority(stack.peek()))//优先级高，入栈
stack.push(i);
else{
while(!stack.isEmpty()&&!stack.peek().equals("(")&&priority(i)<=priority(stack.peek())){
System.out.println(stack.pop());
}
//当前操作符压栈
stack.push(i);
}
}else
throw new RuntimeException("有非法字符");
}
while (!stack.isEmpty())
System.out.println(stack.pop());
}
public static void main(String[] args) {
InfixToPostfix ip=new InfixToPostfix();
String expression=args[0];
ip.transform_pipe(expression);//将中序转为后序，并将结果通过管道送到Evaluate_pipe中进行求解
/*
String expression=null;
while((expression=br.readLine())!=null){
ip.transform_pipe(expression);
}
*/
/* List<String> transform = ip.transform(expression);
for(String i:transform)
System.out.println(i);
}*//*
}catch (Exception e){
e.printStackTrace();
}
*/
}
}