表达式求值

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：

• 数据保证给定的表达式合法。
• 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
• 题目保证表达式中所有数字均为正整数。
• 题目保证表达式在中间计算过程以及结果中，均不超过 231−1231−1。
• 题目中的整除是指向 00 取整，也就是说对于大于 00 的结果向下取整，例如 5/3=15/3=1，对于小于 00 的结果向上取整，例如 5/(1−4)=−15/(1−4)=−1。
• C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 105105。

输入样例：

(2+2)*(1+1)

输出样例：

8

双栈

利用双栈，一个栈保存数字，一个栈保存运算符和括号

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        // 数字栈
        Deque<Integer> stack = new LinkedList<>();
        // 符号栈
        Deque<Character> opStack = new LinkedList<>();
        // 运算的优先级
        Map<Character, Integer> priority = new HashMap<>();
		// 括号不参与运算优先级设置为0,没有括号时,先乘除法再加减法
        priority.put('+', 1);
        priority.put('-', 1);
        priority.put('*', 2);
        priority.put('/', 2);
        priority.put('(', 0);
        priority.put(')', 0);

        int n = s.length();

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            // 如果某个字符是数字,那么把连续的数字转换成运算数
            if (Character.isDigit(c)) {
                int val = 0;
                boolean flag = false;
                while (i < n && Character.isDigit(s.charAt(i))) {
                    val = val * 10 + s.charAt(i) - '0';
                    flag = true;
                    i++;
                }
                if (flag) i--;
                // 将数字加入数字栈
                stack.push(val);
            } else if (c == '(') {// 遇到左括号直接入栈
                opStack.push(c);
            } else if (c == ')') {// 遇到右括号,计算括号里面的加减法,因为在下个部分没有遇到右括号之前,乘除法已经运算完了,所以这边只剩下加减法.
                while (opStack.peek() != '(') {
                    eval(stack, opStack);
                }
                // 左括号出栈
                opStack.pop();
            } else {
                // 计算乘除法
                // 如果符号栈不为空,并且栈顶的优先级大于目前操作符的优先级,那么对当前的符号和数字进行计算
                while (!opStack.isEmpty() && priority.get(opStack.peek()) >= priority.get(c)) {
                    // 计算的应该是乘除法
                    eval(stack, opStack);
                }
                // 把当前的运算符入栈(应该是加减法的符号)
                opStack.push(c);
            }
        }
        // 如果符号栈还没有空,说明还有需要计算的,此时应该只剩下加减法,直接计算即可
        while (!opStack.isEmpty()) {
            eval(stack, opStack);
        }
        System.out.println(stack.pop());
    }

	// 计算模块,计算模块只负责计算,不考虑优先级
    public static void eval(Deque<Integer> stack, Deque<Character> opStack) {
        int op2 = stack.pop();
        int op1 = stack.pop();
        char op = opStack.pop();
        int res = 0;
        switch (op) {
            case '+':
                res = op1 + op2;
                break;
            case '-':
                res = op1 - op2;
                break;
            case '*':
                res = op1 * op2;
                break;
            case '/':
                res = op1 / op2;
                break;
        }

        stack.push(res);
    }

}

赏

谢谢你请我吃糖果

微信