题目描述

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

注意：

• 数据保证给定的表达式合法。

• 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。

• 题目保证表达式中所有数字均为正整数。

• 题目保证表达式在中间计算过程以及结果中，均不超过 231−1。

• 题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。

• C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式
共一行，为给定表达式。

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

数据范围
表达式的长度不超过 105。

样例

(2+2)*(1+1)

8

算法1

参考文献

y总代码

JAVA 代码

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> num = new Stack<>();
        Stack<Character> op = new Stack<>();
        String s = br.readLine();
        int len = s.length();
        Map<Character, Integer> map = new HashMap<>();
        map.put('+',1);
        map.put('-',1);
        map.put('*',2);
        map.put('/',2);
        for (int i = 0; i < len; i++){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                int x = 0, j = i;
                while (j < len && Character.isDigit(s.charAt(j))) x = x * 10 + s.charAt(j++) - '0';
                num.push(x);
                i = j - 1;
            }else if (s.charAt(i) == '('){
                op.push(s.charAt(i));
            }else if (s.charAt(i) == ')'){
                while (op.peek() != '(') eval(num, op);
                op.pop();
            }else if (op.isEmpty()){
                op.push(s.charAt(i));
            }else {//在这里多一个判断，因为优先级中没有存储左括号的优先级，故map会产生空指针异常
                while (!op.isEmpty() && op.peek() != '(' && map.get(op.peek()) >= map.get(s.charAt(i))) eval(num, op);
                op.push(s.charAt(i));
            }
        }
        while (op.size() > 0) eval(num, op);
        System.out.print(num.peek());
    }
    public static void eval (Stack<Integer> num, Stack<Character> op){
        int num1 = num.pop();
        int num2 = num.pop();
        char x = op.pop();
        if(x == '*') num.push(num2 * num1);
        else if (x == '/') num.push(num2 / num1);
        else if (x == '+') num.push(num2 + num1);
        else if (x == '-') num.push(num2 - num1);
    }
}

觉得有帮助来个赞哈,JAVA的兄弟们