题目主要信息

1、给定一个表达式求值

2、字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’,‘(’， ‘)’

3、字符串一定合法

4、可能出现多个数字连在一起组成多位数

5、可能出现负数

方法一:利用栈求解

具体方法

我们可以用o1来储存当前符号，具体定义为

+，o1=1,-,o1=-1

我们通过表达式res=num1+o1×num2来保存当前算式，其中num1为已经计算部分的值，而num2是正在计算部分的值，num1和num2中间由+-隔开

当遇到数字时，我们直接获取数字，并且计算o2，获得num2

当遇到+-时，代表前面的公式已经计算完毕，计算num1，并更新o1，o2，num2

当遇到左括号时，我们要把现在所有结果入栈，并且重置参数

当遇到右括号时，我们要获得当前数字来更新num2

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int calculate (String s) {
        // write code here
        Stack<Integer> stack = new Stack<Integer>();
        // sign 代表正负
        int sign = 1, res = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                int cur = ch - '0';
                while (i + 1 < length && Character.isDigit(s.charAt(i + 1)))
                    cur = cur * 10 + s.charAt(++i) - '0';
                res = res + sign * cur;
            } else if (ch == '+') {
                sign = 1;
            } else if (ch == '-') {
                sign = -1;
            } else if (ch == '(') {
                stack.push(res);
                res = 0;
                stack.push(sign);
                sign = 1;
            } else if (ch == ')') {
                res = stack.pop() * res + stack.pop();
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，时间复杂度和表达式长度正相关
• 空间复杂度：$O(n)O(n)$，需要一个栈，长度和表达式长度正相关

方法二：逆波兰表达式

具体方法

这道题可以通过逆波兰表达式来进行计算。 逆波兰计算器的原理是使用逆波兰表达式来计算出表达式的值，我们人类能够熟练使用的是中缀表达式，比如2×(9+6/3-5)+4就是一个中缀表达式，但是看到上面的简单计算器就知道处理起来很麻烦。于是有一种逆波兰计算器，计算是在逆波兰表达式（也叫做后缀表达式）的基础上。   逆波兰计算器的计算过程为：从左到右扫描后缀表达式，遇到数字就入栈，遇到操作符就从栈弹出两个数字，然后计算得到的值继续入栈，继续扫描表达式，直到扫描完毕得到结果。 从逆波兰计算器的扫描过程可以看到，过程特别简单，代码写起来也比较容易。但现在的难点在于：如何把中缀表达式转成后缀表达式？

  这个过程已经有大神给出来了，我们记下来即可：

  1、初始化两个栈：运算符栈s1和存储中间结果的栈s2；

  2、从左到右扫描中缀表达式；

  3、遇到操作数时，压入到栈s2；

  4、遇到运算符时：

    1）如果s1为空或s1栈顶为左括号"("，则压入到s1；

    2）不满足1），则和s1栈顶运算符比较优先级，高于，则压入s1；

    3）不满足1）和2），弹出s1栈顶运算符并压入到s2，再次回到2）。

  5、遇到右括号")“时，依此弹出s1并压入s2，直到遇到左括号”)"为止，此时丢掉一对括号；

  6、重复2-5，直到扫描完毕；

  7、将s2栈弹出压入到s1，然后s1弹出全部，弹出的顺序即为后缀表达式。

逆波兰表达式应该现在是个常见方法了，大家可以记下来，在这个基础上进行简单修改即可。

Java代码

import java.util.*;

class Solution {
    Map<Character, Integer> map;
    public int calculate(String s) {
        map = new HashMap();
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);
        map.put('(', 3);
        s = s.replaceAll(" ", "");
        String s1 = transfer(s);
        // System.out.println(s1);
        return cal(s1.split(" "));
    }

    String transfer(String s){
        StringBuilder sb = new StringBuilder();
        Deque<Character> stack = new LinkedList<>();
        char[] cs = s.toCharArray();
        int n = cs.length;
        if(n!=0 && !Character.isDigit(cs[0])){
            sb.append("0 ");
        }

        int temp = 0;
        for(int i=0; i<n; i++){
            char c = cs[i];
            if(Character.isDigit(c)){
                temp = temp*10 + (c-'0');
                if(i==n-1 || !Character.isDigit(cs[i+1])){
                    sb.append(temp);
                    sb.append(" ");
                    temp = 0;
                }
            }else if(c=='('){
                stack.push(c);
            }else if(c==')'){
                while(stack.peek()!='('){
                    sb.append(stack.pop());
                    sb.append(" ");
                }
                stack.pop();
            }else{
                while(!stack.isEmpty() && map.get(c)>=map.get(stack.peek())){
                    sb.append(stack.pop());
                    sb.append(" ");
                }
                stack.push(c);
            }
        }
        while(!stack.isEmpty()){
            sb.append(stack.pop());
            sb.append(" ");
        }
        return sb.toString();
    }

     int cal(String[] tokens) {
        Deque<Integer> stack = new LinkedList<>();
        int n = tokens.length;
        String s;
        for(int i=0;i<n;i++){
            s = tokens[i];
            if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
                int a = stack.pop();
                int b = stack.pop();
                stack.push(calculate(a, b, s));
            }else{
                stack.push(Integer.parseInt(s));
            }
        }
        return stack.peek();
    }

    int calculate(int a,int b,String s){
        if(s.equals("+")){
            return a+b;
        }
        if(s.equals("-")){
            return b-a;
        }
        if(s.equals("*")){
            return a*b;
        }
        return b/a;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，时间复杂度和表达式长度正相关
• 空间复杂度：$O(n)O(n)$，需要一个栈，长度和表达式长度正相关