四则运算表达式求值
两个要点
1.中缀表达式转后缀表达式
2.后缀表达式求值

中缀表达式转后缀表达式
从左到右遍历中缀表达式的每个数字和符号.
若是数字就输出,成为后缀表达式的一部分.
若是符号则判断其与栈顶符号的优先级,是右括号或者优先级低于等于栈顶符号,则栈顶元素依次出栈并输出,再将当前的符号进栈。一直到最终输出后缀表达式为止。

后缀表达式求值
从左至右遍历表达式的每个数字和符号,遇到数字就进栈,遇到符号,就弹出栈顶两个元素运算，再将运算结果入栈。一直到最终获得结果。

JDK 1.7+

import java.util.Deque;
import java.util.LinkedList;
public class T {
public static void main(String[] args) {
String target = "9 + ( 3 - 1 ) * 3 + 10 / 2";
System.out.println(calc(target));
}
// 中缀表达式转后缀表达式
private static Deque<String> infixToSuffix(String str) {
Deque<String> result = new LinkedList<String>();
Deque<String> stack = new LinkedList<String>();
String[] tmp = str.split(" ");
for (String c : tmp) {
c = c.trim();
String ele = null;
switch (c) {
case ")":
while (!(ele = stack.removeFirst()).equals("(")) {
if (!ele.equals('(')) {
result.addLast(ele);
}
}
break;
case "(":
stack.addFirst(c);
break;
case "+":
case "-":
while ((ele = stack.peekFirst()) != null) {
if (ele.equals("*") || ele.equals("/") || ele.equals("+") || ele.equals("-")) {
result.addLast(stack.removeFirst());
} else {
break;
}
}
stack.addFirst(c);
break;
case "*":
case "/":
stack.addFirst(c);
break;
default:
result.addLast(c);
break;
}
}
while (!stack.isEmpty()) {
result.addLast(stack.removeFirst());
}
System.out.println(result.toString());
return result;
}
private static Float calc(String str) {
Deque<String> operList = infixToSuffix(str);
Deque<Float> result = new LinkedList<Float>();
while (!operList.isEmpty()) {
String ele = operList.removeFirst();
if (ele.equals("*") || ele.equals("/") || ele.equals("+") || ele.equals("-")) {
Float f1 = result.removeFirst();
Float f2 = result.removeFirst();
switch (ele) {
case "+":
result.addFirst(f2 + f1);
break;
case "-":
result.addFirst(f2 - f1);
break;
case "*":
result.addFirst(f2 * f1);
break;
case "/":
result.addFirst(f2 / f1);
break;
}
} else {
result.addFirst(Float.valueOf(ele));
}
}
return result.removeFirst();
}
}

结果:
[9, 3, 1, -, 3, *, +, 10, 2, /, +]
20.0

ITPub博客

四则运算表达式求值

最新文章