介绍
前缀表达式、中缀表达式、后缀表达式都是四则运算的表达方式,用以四则运算表达式求值,即数学表达式的求职。
中缀表达式
中缀表达式就是常见的运算表达式，如(3+4)×5-6
前缀表达式
前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。
比如:- + 1 × + 2 3 4 5
中缀转前缀
例如:1+((2+3)×4)-5具体过程，如下表
| 扫描到的元素 |
S2(栈底->栈顶) |
S1 (栈底->栈顶) |
说明 |
| 5 |
5 |
空 |
数字，直接入栈 |
| - |
5 |
- |
s1为空，运算符直接入栈 |
| ) |
5 |
-) |
右括号直接入栈 |
| 4 |
5 4 |
-) |
数字直接入栈 |
| x |
5 4 |
-)x |
s1栈顶是右括号，直接入栈 |
| ) |
5 4 |
-)x) |
右括号直接入栈 |
| 3 |
5 4 3 |
-)x) |
数字 |
| + |
5 4 3 |
-)x)+ |
s1栈顶是右括号，直接入栈 |
| 2 |
5 4 3 2 |
-)x)+ |
数字 |
| ( |
5 4 3 2 + |
-)x |
左括号，弹出运算符直至遇到右括号 |
| ( |
5 4 3 2 + x |
- |
同上 |
| + |
5 4 3 2 + x |
-+ |
优先级与-相同，入栈 |
| 1 |
5 4 3 2 + x 1 |
-+ |
数字 |
| 到达最左端 |
5 4 3 2 + x 1 + - |
空 |
s1剩余运算符 |
| 结果是:“- + 1 × + 2 3 4 5” |
|
|
|
计算方式
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
后缀表达式
后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后。
比如:1 2 3 + 4 × + 5 -
中缀转后缀
例如，将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下：
| 扫描到的元素 |
s2(栈底->栈顶) |
s1 (栈底->栈顶) |
说明 |
| 1 |
1 |
空 |
数字，直接入栈 |
| + |
1 |
+ |
s1为空，运算符直接入栈 |
| ( |
1 |
+ ( |
左括号，直接入栈 |
| ( |
1 |
+ ( ( |
同上 |
| 2 |
1 2 |
+ ( ( |
数字 |
| + |
1 2 |
+ ( ( + |
s1栈顶为左括号，运算符直接入栈 |
| 3 |
1 2 3 |
+ ( ( + |
数字 |
| ) |
1 2 3 + |
+ ( |
右括号，弹出运算符直至遇到左括号 |
| × |
1 2 3 + |
+ ( × |
s1栈顶为左括号，运算符直接入栈 |
| 4 |
1 2 3 + 4 |
+ ( × |
数字 |
| ) |
1 2 3 + 4 × |
+ |
右括号，弹出运算符直至遇到左括号 |
| - |
1 2 3 + 4 × + |
- |
-与+优先级相同，因此弹出+，再压入- |
| 5 |
1 2 3 + 4 × + 5 |
- |
数字 |
| 到达最右端 |
1 2 3 + 4 × + 5 - |
空 |
s1中剩余的运算符 |
| 因此结果为“1 2 3 + 4 × + 5 -” |
|
|
|
计算方式
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
实现逆波兰表达式
基于jdk1.8实现的一套代码，兴许有bug，目前遇到。
Formula类，用于存放公式，数据
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
156
157
158
159
160
161
162
| import java.util.ArrayList;
import java.util.List;
import org.apache.commons.lang.StringUtils;
public class Formula {
private String formula = "";
private int parenthesesNum = 0;
private int operatorNum = 0;
private int paraNum = 0;
private List formulaList = new ArrayList();
private List allParaList = new ArrayList();
private String allParas = "";
private String[] allParaArray = null;
private String[] infix = null;
private String[] postfix = null;
private String[] stack = null;
private int stackPointer = -1;
public Formula() {
}
public Formula(String formula) {
this.formula = StringUtils.deleteWhitespace(formula);
this.parseFormula();
this.convertToPostfix();
}
private void parseFormula() {
char chr = false;
StringBuilder tmp = new StringBuilder();
for(int i = 0; i < this.formula.length(); ++i) {
char chr = this.formula.charAt(i);
if (FormulaUtils.isParentheses(chr)) {
++this.parenthesesNum;
this.formulaList.add(String.valueOf(chr));
} else if (FormulaUtils.isOperator(chr)) {
++this.operatorNum;
this.formulaList.add(String.valueOf(chr));
} else {
while(!FormulaUtils.isParentheses(chr) && !FormulaUtils.isOperator(chr)) {
tmp.append(chr);
++i;
if (i >= this.formula.length()) {
break;
}
chr = this.formula.charAt(i);
}
--i;
++this.paraNum;
this.formulaList.add(tmp.toString());
this.allParaList.add(tmp.toString());
tmp.setLength(0);
}
}
this.allParaArray = new String[this.allParaList.size()];
StringBuilder sb = new StringBuilder();
sb.append(this.allParas);
for(int i = 0; i < this.allParaList.size(); ++i) {
sb.append((String)this.allParaList.get(i));
sb.append(",");
this.allParaArray[i] = (String)this.allParaList.get(i);
}
this.allParas = sb.substring(0, sb.length() - 1);
}
private void prepareConvert() {
this.infix = new String[this.parenthesesNum + this.operatorNum + this.paraNum];
this.postfix = new String[this.infix.length - this.parenthesesNum];
this.stack = new String[this.infix.length];
for(int i = 0; i < this.infix.length; ++i) {
this.infix[i] = (String)this.formulaList.get(i);
}
}
private void convertToPostfix() {
this.prepareConvert();
int infixPointer = 0;
int postfixPointer = 0;
while(true) {
while(infixPointer < this.infix.length) {
if (!FormulaUtils.isParentheses(this.infix[infixPointer]) && !FormulaUtils.isOperator(this.infix[infixPointer])) {
this.postfix[postfixPointer] = this.infix[infixPointer];
++infixPointer;
++postfixPointer;
} else if (FormulaUtils.isLeftParentheses(this.infix[infixPointer])) {
this.stackPush(this.infix[infixPointer]);
++infixPointer;
} else if (!FormulaUtils.isRightParentheses(this.infix[infixPointer])) {
if (FormulaUtils.isOperator(this.infix[infixPointer])) {
if (this.stackPointer == -1) {
this.stackPush(this.infix[infixPointer]);
} else if (FormulaUtils.isLeftParentheses(this.stack[this.stackPointer])) {
this.stackPush(this.infix[infixPointer]);
} else if (FormulaUtils.getOperatorPriority(this.infix[infixPointer]) > FormulaUtils.getOperatorPriority(this.stack[this.stackPointer])) {
this.stackPush(this.infix[infixPointer]);
} else {
this.postfix[postfixPointer] = this.stackPop();
this.stackPush(this.infix[infixPointer]);
++postfixPointer;
}
++infixPointer;
}
} else {
while(!FormulaUtils.isLeftParentheses(this.stack[this.stackPointer])) {
this.postfix[postfixPointer] = this.stackPop();
++postfixPointer;
}
this.stackPop();
++infixPointer;
}
}
while(this.stackPointer != -1) {
this.postfix[postfixPointer] = this.stackPop();
++postfixPointer;
}
return;
}
}
private void stackPush(String string) {
++this.stackPointer;
this.stack[this.stackPointer] = string;
}
private String stackPop() {
String string = this.stack[this.stackPointer];
--this.stackPointer;
return string;
}
public String getAllParas() {
return this.allParas;
}
public String[] getAllParaArray() {
return this.allParaArray;
}
public String getPostfix() {
StringBuilder tmp = new StringBuilder();
for(int i = 0; i < this.postfix.length; ++i) {
tmp.append(this.postfix[i]);
tmp.append(",");
}
return tmp.substring(0, tmp.length() - 1);
}
}
|
FormulaCompute类用于计算
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
| import java.math.BigDecimal;
import java.util.HashMap;
public class FormulaCompute {
private String formulaNBL = "";
private HashMap paraValueHash = null;
private String[] postfix = null;
private String[] stack = null;
private String rightOperand = "";
private String leftOperand = "";
private String result = "";
private int postfixPtr = 0;
private int stackPtr = -1;
public FormulaCompute(String formulaNBL, HashMap paraValueHash) {
this.formulaNBL = formulaNBL;
this.paraValueHash = paraValueHash;
this.postfix = this.formulaNBL.split(",");
this.stack = new String[this.postfix.length];
this.replaceParaValue();
}
private void replaceParaValue() {
for(int i = 0; i < this.postfix.length; ++i) {
if (this.paraValueHash.get(this.postfix[i]) != null) {
this.postfix[i] = this.paraValueHash.get(this.postfix[i]).toString();
}
}
}
public String compute() {
for(; this.postfixPtr < this.postfix.length; ++this.postfixPtr) {
if (FormulaUtils.isOperator(this.postfix[this.postfixPtr])) {
this.rightOperand = this.stackPop();
this.leftOperand = this.stackPop();
this.result = this.doCompute(this.postfix[this.postfixPtr], this.rightOperand, this.leftOperand);
this.stackPush(this.result);
} else {
this.stackPush(this.postfix[this.postfixPtr]);
}
}
return this.stackPop();
}
private String doCompute(String operator, String rightOperand, String leftOperand) {
BigDecimal rightDouble = new BigDecimal(rightOperand);
BigDecimal leftDouble = new BigDecimal(leftOperand);
BigDecimal result;
if (operator.equals("+")) {
result = leftDouble.add(rightDouble);
} else if (operator.equals("-")) {
result = leftDouble.subtract(rightDouble);
} else if (operator.equals("*")) {
result = leftDouble.multiply(rightDouble);
} else {
result = leftDouble.divide(rightDouble, 20, 4);
}
return result.toString();
}
private String stackPop() {
String string = this.stack[this.stackPtr];
--this.stackPtr;
return string;
}
private void stackPush(String string) {
++this.stackPtr;
this.stack[this.stackPtr] = string;
}
}
|
使用例子：
1
2
3
4
5
| String formula = "A*(1-B/100)";
HashMap<String, String> formulaValues = new HashMap<String, String>();
formulaValues.put("A", 100 + "");
formulaValues.put("B", 50 + "");
String result = new FormulaCompute(new Formula(formula).getPostfix(), formulaValues).compute();
|
