Java算法题给一个字符串表达式，实现一个基本计算器，返回计算结果

╰半橙微兮° 2024-03-24 15:33 39阅读 0赞

题目：

>     描述
>     给定一个字符串描述的算术表达式，计算出结果值。
>     输入字符串长度不超过 100 ，合法的字符包括 ”+, -, *, /, (, )” ， ”0-9” 。
>     
>     数据范围：运算过程中和最终结果均满足∣val∣≤2^31−1  ，即只进行整型运算，确保输入的表达式合法
>             输入描述：
>             输入算术表达式
>     
>             输出描述：
>             计算出结果值
>     
>             示例1
>             输入：
>             400+5
>             复制
>             输出：
>             405

考点：栈

解题思路：

> 使用 2 个栈，一个 stack\_nums 用来保存计算过程的操作数，一个 stack\_symbol 用来保存运算符。
> 
> 在HashMap中，指定加减优先级为1，乘除优先级为2
> 
> 循环遍历字符串s，
> 
> 1.  操作符入栈：
>     
>     若当前字符为'+', '-', '\*', '/', '(' 时，压入运算符栈 stack\_symbol，
> 2.  操作数入栈：
>     
>     若当前字符为数值类型，相当于循环读取字符串转化为十进制整数，直到下一个字符为非数值类型，把它压入操作数栈中。
> 3.  执行运算：
>     
>     当遍历到加减乘除运算符时，判断栈stack\_symbol内存在优先级大于等于当前运算符，则可以先执行一次运算，尽可能先消费栈stack\_symbol内的运算符；
>     
>     当右括号出现时需要执行一次优先级运算，并从操作符栈内弹出对应的左括号；
> 4.  运算规则：栈是后进先出，参与加减乘除运算时，第一个从 stack\_nums 栈顶弹出的数应在运算符后面，第二个 stack\_nums 从栈顶弹出的数应在运算符前面。
> 
> 1.  特殊情况处理：
> 
>  *  括号的处理：
> 
> 括号有2种情况，
> 
> 第一种是负数携带的括号，即除了第一个位置出现的数外，后面的数为负数时所附带的括号，
> 
> 第二种是，需要优先进行运算的式子
> 
>  *  负数的处理：
> 
> 对于负数的处理，增加一步 0 - n 运算，假设负号后面的数等于 n
> 
> 开头第一个数带 '-' 号，s.charAt(0) == '-'
> 
> s = "0" + s;
> 
> 或者括号 () 里面第一个数带 '-' 号，
> 
> s = s.replace( "(-", "(0-" );
> 
> 认为是负号，否则认为是减号
> 
> 当循环结束时，若栈stack\_symbol内还有运算符，继续算完

import java.util.Scanner;
    import java.util.Stack;
    import java.util.Map;
    import java.util.HashMap;
    
    // 注意类名必须为 Main, 不要有任何 package xxx 信息
    /**
     * @ClassName
     * @Description
     * @Author liulvhua
     * @Date 2023/4/5
     **/
    public class HJ54 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            Stack<Integer> stack_nums = new Stack<>();
            Stack<Character> stack_symbol = new Stack<>();
            Map<Character, Integer> map = new HashMap<>();
            map.put('+', 1);
            map.put('-', 1);
            map.put('*', 2);
            map.put('/', 2);
            while (sc.hasNextLine()) {
                String s = sc.nextLine();
                if (s.charAt(0) == '-') {//第一个数为负数
                    s = "0" + s;
                }
                s = s.replace("(-", "(0-");//其他位置负数处理
                for (int i = 0; i < s.length(); i++) {
                    char ch = s.charAt(i);
                    if (ch == ' ') continue;
                    if (ch == '(') {
                        stack_symbol.push(ch);
                        continue;
                    }
                    if (ch == ')') {
                        //括号结束计算一次
                        stack_nums.push(calculate(stack_nums, stack_symbol));
                        if (!stack_symbol.isEmpty() && stack_symbol.peek() == '(') {
                            //当前计算是括号内最后一次运算，弹出左括号
                            stack_symbol.pop();
                        }
                        continue;
                    }
                    if (map.containsKey(ch)) {
                        // 栈内至少有1个运算符且栈顶不是左括号，并且栈内运算符优先级大于等于当前运算符号优先级，执行一次计算，
                        // 即先消费已入栈的高优先级运算符
                        while (!stack_symbol.isEmpty() && stack_symbol.peek() != '(' && map.get(stack_symbol.peek()) >= map.get(ch)) {
                            stack_nums.push(calculate(stack_nums, stack_symbol));
                        }
                        stack_symbol.push(ch);
                    } else {
                        int num = 0;
                        int j = i;//循环读取十进制整数
                        while (j < s.length() && Character.isDigit(s.charAt(j))) {
                            num = num * 10 + s.charAt(j) - '0';
                            j++;
                        }
                        stack_nums.push(num);
                        i = j - 1;
                    }
                }
                // 循环结束还有未算尽的式子，优先级低
                while (!stack_symbol.isEmpty()) {
                    stack_nums.push(calculate(stack_nums, stack_symbol));
                    if (!stack_symbol.isEmpty() && stack_symbol.peek() == '(') {
                        stack_symbol.pop();
                    }
                }
                System.out.println(stack_nums.pop());
            }
        }
    
        /**
         * 执行运算
         * @param stack_nums 操作数栈
         * @param stack_symbol 运算符栈
         * @return
         */
        public static int calculate(Stack<Integer> stack_nums, Stack<Character> stack_symbol) {
            int res = 0;
            int opt_nums2 = stack_nums.pop();
            int opt_nums1 = stack_nums.pop();
            char symbol = stack_symbol.pop();
            switch (symbol) {
                case '+': {
                    res = opt_nums1 + opt_nums2;
                    break;
                }
                case '-': {
                    res = opt_nums1 - opt_nums2;
                    break;
                }
                case '*': {
                    res = opt_nums1 * opt_nums2;
                    break;
                }
                case '/': {
                    res = opt_nums1 / opt_nums2;
                    break;
                }
            }
            return res;
        }
    }

执行用例：

> 2\*3-2\*(1-2\*2)-0  
> 12  
> 2\*3-2\*(1-2\*(1-3))-0  
> \-4  
> 2\*3-2\*(1-2\*(1-3))-0  
> \-4  
> 2\*3-2\*(1-2\*(1-3)\*(-1))-0  
> 12