题目：

给定一个字符串形式的表达式 s ，请你实现一个计算器并返回结果。字符串中包含 + , - , ( , ) ，保证表达式合法。

方法一：去括号

本题只有4种符号'+','-','(',')',当我们计算有括号的字符串时首先想到如何处理括号，比如'3+(5-(3-1))',可以去掉括号，变成计算'3+5-3+1',也就是说遇到括号时需要将括号内的符号变号，怎么去掉括号呢?我们用{+1，-1}分别表示操作符'+'和'-'，

先初始化栈顶元素为1即表示'+'
当c='+',取栈顶元素为操作符
当c='-'，取栈顶元素为反
当c='('，将此时的op进栈，
当c=')'，已经用过的op出栈
遇到数字，则计算数字，如果数字大于9，则需要用num保存计算

举个例子，'3+(5-(3-1))'：

遇到'+'，op=1,遇到第一个'('，会把'('左边的运算符符1('+')进栈ops，相当于去掉左边的第一个括号，遇到5时出栈运算符，相当于计算res=3+5=8，
遇到'-',op=-ops.peekFirst()=-1,当遇到第二个'('，会把-1（'-'）进栈，再次遇到数字3时相当于计算res=8-3=5，
再遇到'-'时，op=-ops.peekFirst()=1，遇到1出栈运算符，相当于计算res=5+1=6,遇到')'，把栈中元素出栈

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int calculate (String s) {
        // write code here
        int op=1;
        Deque<Integer>ops=new LinkedList<>();
        ops.add(1);
        int res=0;
        int num=0;
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(c=='+')op=ops.peekLast();
            else if(c=='-')op=-ops.peekLast();
            else if(c=='(')ops.addLast(op);
            else if(c==')')ops.removeLast();
            else if(Character.isDigit(c)){
                int j=i;
                while(j<s.length()&&Character.isDigit(s.charAt(j))){num=num*10+s.charAt(j)-'0';j++;}
                i=j-1;
                res+=op*num;
                num=0;
            }
        }
        return res;

    }
}

复杂度：

时间复杂度： $O (n)$ ,遍历字符串一次
空间复杂度： $O (n)$ ，额外开辟栈的空间

方法二：双栈

nums栈存储操作数，ops栈存储运算符，

当遇到左括号直接进ops栈
遇到右括号，一直出栈ops中的运算符，计算括号内能够计算的，定义一个cal函数进行计算；直到遇到左括号，左括号出栈
遇到数字继续计算，并将数字进nums栈
遇到运算符，如果运算符的前一位是'(',或者'-'，往nums栈中接入一个0，例如1-(-2)，变成1-(0-2),当
运算符栈非空而且栈顶不是左括号（如果是左括号则要先计算左括号里的不能在这里直接计算），把可以计算的先进行计算
如果ops栈还没空，继续出栈计算，最后的到的结果存储在nums栈栈顶

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int calculate (String s) {
        // write code here
        Deque<Integer>nums=new LinkedList<>();
        Deque<Character>ops=new LinkedList<>();
        for(int i=0;i<s.length();i++){
            char c=s.charAt(i);
            if(c=='('){
                ops.addLast(c);
            }
            else if(c==')'){//遇到右括号，把栈中能计算的先计算
                while(!ops.isEmpty()){
                    if(ops.peekLast()!='(')
                        cal(nums,ops);
                    else{
                        ops.removeLast();
                        break;
                    }
                }
            }
            else {
                if(Character.isDigit(c)){//遇到数字，计算数字并进栈
                    int j=i;
                    int num=0;
                    while(j<s.length()&&Character.isDigit(s.charAt(j))){num=num*10+s.charAt(j)-'0';j++;}
                    nums.addLast(num);
                    i=j-1;
                }
                else {//遇到运算符
                    //如果遇到类似于(-2,可以转换为(0-2，往nums栈中添加一个数字
                    if(i>0&&(s.charAt(i-1)=='+'||s.charAt(i-1)=='-'||s.charAt(i-1)=='('))nums.addLast(0);
                    //如果第一个数时负数，nums中先添加0
                    if(i==0&&s.charAt(i)=='-')nums.addLast(0);
                    //当运算符栈不空且第一个不是'('，可以进行计算
                    while(!ops.isEmpty()&&ops.peekLast()!='(')cal(nums,ops);
                    ops.addLast(c);//运算符需要进栈
                }
            }
        }
        while(!ops.isEmpty())cal(nums,ops);//当运算符栈未空继续计算
        return nums.peekLast();

    }
    void cal(Deque<Integer>nums,Deque<Character>ops){
        if(nums.isEmpty()||nums.size()<2)return;
        if(ops.isEmpty())return;
        int b=nums.removeLast();
        int a=nums.removeLast();
        int num=ops.removeLast()=='+'?a+b:a-b;
        nums.addLast(num);

    }
}

复杂度：

时间复杂度： $O (n)$ ，遍历字符串一次
空间复杂度： $O (n)$ ，nums栈和ops栈需要一定空间

题解 | #计算器(一)#

题目：

方法一：去括号

复杂度：

方法二：双栈

复杂度：