前缀表达式：
前缀表达式是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3。
中缀表达式：
中缀表达式是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。
后缀表达式：
逆波兰式（Reverse Polish Notation，RPN，或逆波兰记法），也叫后缀表达式，它将运算符写在操作数之后（例：1 2 3 + 4 * + 5 –）。
代码：
1 import cn.hutool.core.collection.CollUtil;
2 import cn.hutool.core.util.StrUtil;
3 import java.math.BigDecimal;
4 import java.util.ArrayList;
5 import java.util.List;
6 import java.util.Stack;
7 import java.util.regex.Pattern;
8
9 public class InversePolishCalculatorTest {
10 public static void main(String[] args) {
11
12 InversePolishCalculator calculator = new InversePolishCalculator();
13 // String infixStr1 = "( 3 + 4 ) * 5 - 6";
14 // String infixStr2 = "1 + ( ( 2 + 3 ) * 4 ) - 5";
15 // String infixStr3 = "12.8 + ( 2 - 3.55 ) * 4 + 10 / 5.0";
16 // String infixStr4 = "36.8 + ( -12 - 4 ) * 2";
17 // String infixStr5 = "-10.5 - 3 * 8";
18 // try {
19 // System.out.println(CalcUtil.isNumber("3"));
20 // BigDecimal result1 = calculator.getResult(infixStr1);
21 // System.out.println("result1:" + result1);
22 // } catch (Exception e) {
23 // System.out.println(e.getMessage());
24 // }
25 // try {
26 // BigDecimal result2 = calculator.getResult(infixStr2);
27 // System.out.println("result2:" + result2);
28 // } catch (Exception e) {
29 // System.out.println(e.getMessage());
30 // }
31 // try {
32 // BigDecimal result3 = calculator.getResult(infixStr3);
33 // System.out.println("result3:" + result3);
34 // } catch (Exception e) {
35 // System.out.println(e.getMessage());
36 // }
37 // try {
38 // BigDecimal result4 = calculator.getResult(infixStr4);
39 // System.out.println("result4:" + result4);
40 // } catch (Exception e) {
41 // System.out.println(e.getMessage());
42 // }
43 // try {
44 // BigDecimal result5 = calculator.getResult(infixStr5);
45 // System.out.println("result5:" + result5);
46 // } catch (Exception e) {
47 // System.out.println(e.getMessage());
48 // }
49 String infixStr1 = "( --3 + 4 ) * 5 - 6";
50 String infixStr2 = "1.0.1 + ( ( 2 + 3 ) * 4 ) - 5";
51 String infixStr3 = "12.8 + ( ab - 3.55 ) * 4 + 10 / 5.0";
52 String infixStr4 = "36.8 + ( -12 ++ 4 ) * 2";
53 String infixStr5 = "";
54 try {
55 System.out.println(CalcUtil.isNumber("3"));
56 BigDecimal result1 = calculator.getResult(infixStr1);
57 System.out.println("result1:" + result1);
58 } catch (Exception e) {
59 System.out.println(e.getMessage());
60 }
61 try {
62 BigDecimal result2 = calculator.getResult(infixStr2);
63 System.out.println("result2:" + result2);
64 } catch (Exception e) {
65 System.out.println(e.getMessage());
66 }
67 try {
68 BigDecimal result3 = calculator.getResult(infixStr3);
69 System.out.println("result3:" + result3);
70 } catch (Exception e) {
71 System.out.println(e.getMessage());
72 }
73 try {
74 BigDecimal result4 = calculator.getResult(infixStr4);
75 System.out.println("result4:" + result4);
76 } catch (Exception e) {
77 System.out.println(e.getMessage());
78 }
79 try {
80 BigDecimal result5 = calculator.getResult(infixStr5);
81 System.out.println("result5:" + result5);
82 } catch (Exception e) {
83 System.out.println(e.getMessage());
84 }
85 }
86 }
87
88 /**
89 * 逆波兰计算器
90 */
91 class InversePolishCalculator {
92
93 /**
94 * 中缀转后缀
95 * @param infixStr ( 3 + 4 ) * 5 - 6
96 * @return 后缀表达式的集合
97 */
98 private List<String> infixToSuffix(String infixStr) throws Exception {
99 if (StrUtil.isBlank(infixStr)) {
100 System.out.println("中缀表达式为空，无法转换");
101 return null;
102 }
103 String[] infixArray = infixStr.split(" ");
104
105 //1:初始化运算符栈operStack和储存中间结果的cachList；
106 Stack<String> operStack = new Stack<>();
107 List<String> cachList = new ArrayList<>(infixArray.length);
108 //2:从左至右扫描中缀表达式；
109 for (int i = 0; i < infixArray.length; i++) {
110 if (CalcUtil.isNumber(infixArray[i])) {
111 //3:遇到操作数时，将其放入cachList；
112 cachList.add(infixArray[i]);
113 } else if (CalcUtil.isSymbol(infixArray[i])) {
114 //4:遇到运算符时，比较其与operStack栈顶运算符的优先级：
115 if (operStack.empty() || CalcUtil.LEFT_BRACKET.equals(operStack.peek())) {
116 //4.1：如果operStack为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈operStack；
117 operStack.push(infixArray[i]);
118 } else if (CalcUtil.getLevel(infixArray[i]) > CalcUtil.getLevel(operStack.peek())) {
119 //4.2：否则，若优先级比栈顶运算符的高，也将运算符压入operStack；
120 operStack.push(infixArray[i]);
121 } else {
122 //4.3：否则，将operStack栈顶的运算符弹出并放入到cachList中，再次转到(4.1)与operStack中新的栈顶运算符相比较；
123 while (!operStack.empty()
124 && !CalcUtil.LEFT_BRACKET.equals(operStack.peek())
125 && CalcUtil.getLevel(infixArray[i]) <= CalcUtil.getLevel(operStack.peek())) {
126 cachList.add(operStack.pop());
127 }
128 operStack.push(infixArray[i]);
129 }
130 } else if (CalcUtil.isBracket(infixArray[i])){
131 //5:遇到括号时：
132 if (CalcUtil.LEFT_BRACKET.equals(infixArray[i])) {
133 //5.1:如果是左括号“(”，则直接压入operStack；
134 operStack.push(infixArray[i]);
135 } else {
136 //5.2:如果是右括号“)”，则依次弹出operStack栈顶的运算符，并放入cachList，直到遇到左括号为止，此时将这一对括号丢弃；
137 while (!CalcUtil.LEFT_BRACKET.equals(operStack.peek())) {
138 cachList.add(operStack.pop());
139 }
140 operStack.pop();
141 }
142 } else {
143 throw new Exception("中缀表达式有误");
144 }
145 }
146 //6：重复步骤2至5，直到表达式的最右边；
147 //7：将operStack中剩余的运算符依次弹出并放入cachList；
148 while (!operStack.empty()) {
149 cachList.add(operStack.pop());
150 }
151 //8：cachList即为中缀表达式对应的后缀表达式；
152 return cachList;
153 }
154
155 /**
156 * 计算后缀表达式
157 * @param suffixList [3,4,+,5,*,6,-]
158 * @return
159 */
160 private BigDecimal calcuSuffix(List<String> suffixList) throws Exception {
161 if (CollUtil.isEmpty(suffixList)) {
162 throw new Exception("后缀表达式为空，无法计算");
163 }
164 Stack<String> stack = new Stack<>();
165 BigDecimal result = null;
166 //遇到数则入栈，遇到运算符则从栈中弹出两个值用这个运算符计算，并将结果入栈
167 for (String str : suffixList) {
168 if (CalcUtil.isNumber(str)) {
169 stack.push(str);
170 } else if (CalcUtil.isSymbol(str)) {
171 BigDecimal firstNum = new BigDecimal(stack.pop());
172 BigDecimal secondNum = new BigDecimal(stack.pop());
173
174 switch (str) {
175 case CalcUtil.ADD :
176 result = secondNum.add(firstNum);
177 break;
178 case CalcUtil.MINUS :
179 result = secondNum.subtract(firstNum);
180 break;
181 case CalcUtil.MULTIPLY :
182 result = secondNum.multiply(firstNum);
183 break;
184 default:
185 result = secondNum.divide(firstNum);
186 break;
187 }
188 stack.push(result.toString());
189 } else {
190 throw new Exception("后缀表达式有误，无法计算");
191 }
192 }
193 //直到suffixList没有元素了，那么栈中唯一的值就是表达式的结果
194 return new BigDecimal(stack.pop()).setScale(2,BigDecimal.ROUND_HALF_UP);
195 }
196
197 /**
198 * 获取中缀表达式的结果
199 * @param infixStr ( 3 + 4 ) * 5 - 6
200 * @return
201 */
202 public BigDecimal getResult(String infixStr) throws Exception {
203 List<String> suffixList = infixToSuffix(infixStr);
204 return calcuSuffix(suffixList);
205 }
206 }
207
208 /**
209 * 计算器工具类
210 */
211 class CalcUtil {
212
213 /**
214 * 运算符 （
215 */
216 public static final String LEFT_BRACKET = "(";
217
218 /**
219 * 运算符 ）
220 */
221 public static final String RIGHT_BRACKET = ")";
222
223 /**
224 * 运算符 +
225 */
226 public static final String ADD = "+";
227
228 /**
229 * 运算符 -
230 */
231 public static final String MINUS= "-";
232
233 /**
234 * 运算符 *
235 */
236 public static final String MULTIPLY = "*";
237
238 /**
239 * 运算符 /
240 */
241 public static final String DIVISION = "/";
242
243 /**
244 * 判断是不是数
245 * @param str
246 * @return
247 */
248 public static boolean isNumber(String str) throws Exception {
249 if (StrUtil.isBlank(str)) {
250 throw new Exception("isNumber:输入参数为空");
251 }
252 Pattern pattern = Pattern.compile("-?[0-9]+(.[0-9]+)?");
253 return pattern.matcher(str).matches();
254 }
255
256 /**
257 * 判断是不是运算符
258 * @param str
259 * @return
260 */
261 public static boolean isSymbol(String str) throws Exception {
262 if (StrUtil.isBlank(str)) {
263 throw new Exception("isSymbol:输入参数为空");
264 }
265 return str.matches("\\+|-|\\*|/");
266 }
267
268 /**
269 * 判断是不是括号
270 * @param str
271 * @return
272 */
273 public static boolean isBracket(String str) throws Exception {
274 if (StrUtil.isBlank(str)) {
275 throw new Exception("isBracket:输入参数为空");
276 }
277 return str.matches("\\(|\\)");
278 }
279
280 /**
281 * 获取运算符的优先级
282 * @param str
283 * @return
284 */
285 public static int getLevel(String str) throws Exception {
286 if (StrUtil.isBlank(str)) {
287 throw new Exception("getLevel:输入参数为空");
288 }
289
290 int level = 0;
291 switch(str){
292 case ADD :
293 case MINUS :
294 level = 1;
295 break;
296 case MULTIPLY :
297 case DIVISION :
298 level = 2;
299 break;
300 default:
301 throw new Exception("getLevel:输入参数有误");
302 }
303 return level;
304 }
305 }
标签：Exception,String,System,运算符,波兰,计算,println,表达式,out From： https://www.cnblogs.com/xueseng/p/17058478.html