Java 四则运算表达式解析算法
四则运算表达式解析
问题
给出任意的四则运算算数表达式都可以得到其正确的结果，例如：表达式5*7+2-4*(3*2+5*4-2)-7-(4+2*5)该表达式的结果为-80。
思路
使用两个栈对表达式进行解析。 解析规则如下
- 遇到数字压入数字（不限大小只限正数）
- 遇到左括号（，直接压入字符栈
- 遇到右括号），弹出数字栈中两个数字弹出字符栈中一个字符进行运算，直到遇到左括号为止
- 分配优先级+-/，其中+-优先级为1，/优先级为2
- 遇到运算符，分以下几种情况
- 字符栈为空，直接压入
- 字符栈栈顶为左括号（，直接压入
- 字符栈栈顶优先级小于等于（<=）压入字符的优先级，则弹出数字栈两个数字弹出字符栈字符进行运算，结果压入到数字栈
- 字符栈栈顶优先级大于（>）压入字符的优先级，直接压入字符栈
图解
按照以上规则进行实现
代码实现
public class StackTest {
public static final Map<Character,Integer> ORDER = new HashMap<>();
static {
ORDER.put('+',1);
ORDER.put('-',1);
ORDER.put('*',2);
ORDER.put('/',2);
}
public static void main(String[] args) {
Stack<Integer> numberStack = new Stack<>();
Stack<Character> operationStack = new Stack<>();
String operation = new Scanner(System.in).next();
// 记录 (
char topOperation = '0';
// 扫描operation表达式
for (int i = 0; i < operation.length(); i++) {
// 处理数字
if(Character.isDigit(operation.charAt(i))){
// 不限制数字大小 限制数字是正整数
Integer number = seeNumber(operation,i);
i += String.valueOf(number).length()-1;
// 压入数字栈
numberStack.push(number);
continue;
}
// 运算符 且 符号栈为空 && 符号为( 直接入栈
if(operationStack.isEmpty() || operation.charAt(i) == '('){
operationStack.push(operation.charAt(i));
continue;
}
if(operation.charAt(i) == ')'){
Character pop = null;
// 右括号时 将子表达式结果求出并压入数字栈
while((pop = operationStack.pop()) != '('){
Integer pop1 = numberStack.pop();
Integer pop2 = numberStack.pop();
numberStack.push(ys(pop2,pop1,pop));
}
continue;
}
// 栈顶运算符是左括号 则当前的运算符直接压入符号栈
if((topOperation = operationStack.pop()) == '('){
operationStack.push(topOperation);
operationStack.push(operation.charAt(i));
continue;
}
operationStack.push(topOperation);
// 弹栈运算操作
if(!operationStack.isEmpty()){
// 拿到栈顶运算符
Character pop = operationStack.pop();
// 比较优先级 准备压入的字符优先级大于栈顶运算符优先级时直接压入准备压入的字符串
if (ORDER.get(pop) < ORDER.get(operation.charAt(i))) {
operationStack.push(pop);
operationStack.push(operation.charAt(i));
continue;
}
// 准备弹栈运算操作
do{
// 必要的弹出两个数字进行运算
Integer pop1 = numberStack.pop();
Integer pop2 = numberStack.pop();
Integer res = ys(pop2,pop1,pop);
numberStack.push(res);
pop = operationStack.pop();
// 优先级一致时继续运算
}while ((ORDER.get(operation.charAt(i)).equals(ORDER.get(pop))));
// 栈不为空则最后一个弹出的运算符再压入到字符栈中
if(pop != null){
operationStack.push(pop);
}
operationStack.push(operation.charAt(i));
}
}
// 最后将两个栈进行运算，得到最后的运算结果
while(!operationStack.isEmpty()){
Integer pop1 = numberStack.pop();
Integer pop2 = numberStack.pop();
Integer res = ys(pop2,pop1,operationStack.pop());
numberStack.push(res);
}
// 数字栈第一个为最终运算结果
System.out.println(operation + "=" + numberStack.pop());
}
// 扫描数字到不是数字为之
private static Integer seeNumber(String operation, int j) {
StringBuilder sb = new StringBuilder();
for (int i = j; i < operation.length(); i++) {
if(Character.isDigit(operation.charAt(i))){
sb.append(operation.charAt(i));
}else{
break;
}
}
return Integer.parseInt(sb.toString());
}
// 运算
private static Integer ys(Integer a, Integer b, Character pop2) {
switch (pop2){
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
default:
return a/b;
}
}
}
运算结果：
5*7+2-4*(3*2+5*4-2)-7-(4+2*5)
5*7+2-4*(3*2+5*4-2)-7-(4+2*5)=-80