题解 | #表达式求值#

HJ54 表达式求职

题目描述

给定一个字符串描述的算术表达式，计算出结果值。

输入字符串长度不超过 100 ，合法的字符包括 ”+, -, *, /, (, )” ， ”0-9” 。

方法一：暴力算法

解题思路

对于方法一，我们直接使用JavaScript中console类的log函数，并且其参数为eval(str)，其中eval()函数会将传入的字符串进行转换。这样直接利用最无脑暴力的代码来进行本题的求解。

解题代码

let str = readline() // 读字符串
console.log(eval(str))  // 暴力方法解决问题

复杂度分析

时间复杂度：eval()函数一层循环，时间复杂度为$O(N)O(N)$。

空间复杂度：对于暴力求解，没有引入新的地址空间，因此空间复杂度为$O(1)O(1)$

方法二：栈的思想

解题思路

对于本题目的求解，我们自然想到运算符的计算首先需要考虑优先级，其次考虑到括号匹配的问题，因此我们使用栈的思想来进行括号匹配，然后对于运算符的优先级问题则声明一个map来对加减乘除的优先级进行声明。对于输入的序列，先对括号里面的数字进行压栈，遇到右括号以后进行括号匹配，进行括号内的算术运算，以此类推，最终将表达式进行求值。

解题代码

import java.util.*;
public class Main {
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String expression = sc.nextLine();
        System.out.println(calculate(expression));
    }
    public static Map<Character, Integer> map = new HashMap<Character, Integer>()
    { // 声明优先级
        {
        put('-', 1);
        put('+', 1);
        put('*', 2);
        put('/', 2);
        }
    };
    public static int calculate(String s)
    {
        s = s.replaceAll(" ", "");
        s = s.replaceAll("\\(-", "(0-");
        s = s.replaceAll("\\(\\+", "(0+");
        char[] cs = s.toCharArray();
        int n = s.length();
        // 存放所有的数字
        stack<Integer> nums = new stack<>();
        // 为了防止第一个数为负数，先往 nums 加个 0
        nums.addLast(0);
        // 存放所有「非数字以外」的操作
        stack<Character> ops = new stack<>();
        for (int i = 0; i < n; i++)
        {
            char c = cs[i];
            if (c == '(')
            {
                ops.addLast(c);
            } else if (c == ')')
            {
                // 计算到最近一个左括号为止
                while (!ops.isEmpty())
                {
                    if (ops.peekLast() != '(')
                    {
                        calc(nums, ops);
                    } else
                    {
                        ops.pollLast();
                        break;
                    }
                }
            }
            else
            {
                if
                    (isNumber(c))
                {
                    int u = 0;
                    int j = i;
                    // 将从 i 位置开始后面的连续数字整体取出，加入 nums
                    while (j < n && isNumber(cs[j]))
                    {
                        u = u * 10 + (cs[j++] - '0');
                    }
                    nums.addLast(u);
                    i = j - 1;
                }
                else
                {
                    // 有一个新操作要入栈时，先把栈内可以算的都算了
                    // 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
                    while (!ops.isEmpty() && ops.peekLast() != '(') {
                        char prev = ops.peekLast();
                        if (map.get(prev) >= map.get(c)) {
                            calc(nums, ops);
                        } else {
                            break;
                        }
                    }
                    ops.addLast(c);
                }
            }
        }
        // 将剩余的计算完
        while (!ops.isEmpty()) {
            calc(nums, ops);
        }
        return nums.peekLast();
    }
    public static void calc(stack<Integer> nums, stack<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) {
            return;
        }
        if (ops.isEmpty()) {
            return;
        }
        int b = nums.pollLast(), a = nums.pollLast();
        char op = ops.pollLast();
        int ans = 0;
        switch (op) {
            case '+':
                ans = a + b;
                break;
            case '-':
                ans = a - b;
                break;
            case '*':
                ans = a * b;
                break;
            case '/':
                ans = a / b;
            default:
                break;
        }
        nums.addLast(ans);
    }
    public static boolean isNumber(char c) {
        return Character.isDigit(c);
    }
}

复杂度分析

时间复杂度：一层循环，因此时间复杂度为$O(N)O(N)$

空间复杂度：nums队列申请地址空间，因此空间复杂度为$O(N)O(N)$