AcWing.表达式求值模板题

发布时间:2024年01月24日

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

注意:

  • 数据保证给定的表达式合法。
  • 题目保证符号?-?只作为减号出现,不会作为负号出现,例如,-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.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        //读入输入的字符串表达式
        String s = sc.next();
        Map<Character,Integer> map = new HashMap<>();
        map.put('+',1);
        map.put('-',1);
        map.put('*',2);
        map.put('/',2);

        Stack<Character> op = new Stack<>(); //存字符
        Stack<Integer> num = new Stack<>();    //存数字

        //循环遍历每一位字符
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            //数字可能存在多位
            if (Character.isDigit(c)){
                int x = 0;  //x用来放入栈的数字 (数字不一定只有一位)
                int j = i;

                //要判断当前这个字符是不是数字,不能直接把c拿来判断
                while (j < s.length() && Character.isDigit(s.charAt(j))){
                    x = x * 10 + s.charAt(j) - '0';
                    j++;
                }
                //while循环退出后的x即为要入栈的数字
                num.push(x);
                //此时的j指向新的一个字符(即x末尾数字的下一个),但最外层的for循环会对i自增
                //只需要让i指向x的最后一位即可
                i = j - 1;
            } else if( c == '('){
                //左括号直接入栈即可
                op.push(c);
            } else if( c == ')'){
                //如果是右括号,因为括号的优先级最高,所以此时不需要考虑栈的优先级问题
                //直接把两个括号间的内容进行计算
                while (op.peek() != '('){
                    //这里只是对+-*/弹出,对于(并没有处理,在while外层还需要单独对while处理
                    eval(op,num);
                }

                //将左括号弹出
                op.pop();
            }else {
                //正常字符的话: 栈顶元素的优先级 >= 当前元素的优先级,就计算
                //否则就入栈
                //栈内元素计算的前提是栈不能为空
                //左括号以左的内容不能碰,
                while (!op.empty() && op.peek() != '('
                && map.get(op.peek()) >= map.get(c)){
                    eval(op,num);
                }
                op.push(c);
            }
        }
        //最后把字符栈里的所有元素直接计算
        while (!op.empty()) eval(op,num);
        System.out.println(num.peek());
    }
    public static void eval(Stack<Character> chars, Stack<Integer> nums){
        int b = nums.pop();
        int a = nums.pop();

        char c = chars.pop();
        if (c == '+'){
            nums.push(a + b);
        } else if (c == '-'){
            nums.push(a - b);
        }else if (c == '*'){
            nums.push(a * b);
        }else{
            nums.push(a / b);
        }
    }
}

文章来源:https://blog.csdn.net/2302_76649176/article/details/135823337
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。