题解 | #表达式求值#

描述
请写一个整数计算器，支持加减乘三种运算和括号。
示例

输入：
"1+2"
返回值：
3

思路：
题目给出了一个中缀表达式，要我们求表达式的结果，最直接的想法就是把中缀表达式转为后缀表达式，再利用一个栈完成后缀表达式的求值。
方法一：中缀表达式转后缀表达式+后缀表达式求值
中缀表达式转后缀表达式：

• 定义一个保存运算符的优先级，乘除优先级高于加减
• 定义一个动态数组保存后缀表达式，运算符栈存储运算符
• 遇到左括号时直接入运算符栈，遇到右括号时不断弹出栈中的运算符，并将其加入后缀表达式直到左括号出栈，左括号不加入后缀表达式
• 遇到操作数时，如果是多位数则需要将连续的多个数字取出，使用u保存整个数字字符串，并将数字字符串加入后缀表达式

后缀表达式求值：

先定义一个栈，遍历后缀表达式数组，遇到数字则将其转换为整型并入栈，遇到运算符则弹出栈顶元素，先弹出的数字为右操作数，后弹出的数字为左操作数，将计算结果入栈，直到遍历完后缀表达式，此时栈中的元素即为后缀表达式的结果，将计算结果出栈。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    Map<Character,Integer>map=new HashMap<Character,Integer>();
    public int solve (String s) {
    // write code here
        //去除所有空格
        s=s.replaceAll(" ","");
        //用一个hashmap保存运算符的优先级
        map.put('+',1);
        map.put('-',1);
        map.put('*',2);
        map.put('/',2);
        //保存后缀表达式的数组
        ArrayList<String>list=new ArrayList();
        //保存运算符的栈
        Stack<Character>operation=new Stack<>();
        int i;
        for(i=0;i<s.length();i++){
            Character c=s.charAt(i);
            //计算操作数的值
            if(isNumber(c)){
            String u="";
            int j=i;
            //从i位置开始后面的连续数字整体取出，加入nums
            while(j<s.length()&&isNumber(s.charAt(j)))u+=Character.toString(s.charAt(j++));
            list.add(u);
            //更新i的值，因为i会自增，所以这里i=j-1
            i=j-1;
            }
            //左括号直接入栈
            else if(c=='(')operation.push(c);
            //遇到右括号，弹出栈中的运算符直到遇到左括号，运算符加入后缀表达式，左括号也需要出栈，但是左括号不需加入后缀表达式
            else if(c==')')
            {
                Character c2;
                while((c2=operation.pop())!='(')
                {
                    list.add(c2.toString());
                }
            }
            else {
                    //遇到运算符时，栈非空而且栈顶运算符优先级高于当前运算符，将运算符出栈并加入后缀表达式
                    //当栈顶元素为左括号时，条件不成立，当前运算符应该直接入栈
                    while(!operation.isEmpty()&&map.containsKey(operation.peek())&&map.get(operation.peek())>=map.get(c))
                            list.add(operation.pop().toString());
                    //将当前运算符入栈
                    operation.push(c);
                }
        }
        //将栈中的剩余运算符出栈并且加入后缀表达式中
        while(!operation.isEmpty())list.add(operation.pop().toString());
        Stack<Integer>number=new Stack<>();
        for(String str:list){
            if(!(str.equals("+")||str.equals("-")||str.equals("*")||str.equals("/")))number.push(Integer.valueOf(str));
            else{

                //先出栈的数字为右操作数，后出栈的为左操作数
                int num2=number.pop();
                int num1=number.pop();
                switch(str){
                //每次将运算结果压入栈
                    case "+":number.push(num1+num2);break;
                    case "-":number.push(num1-num2);break;
                    case "*":number.push(num1*num2);break;
                    case "/":number.push(num1/num2);break;
                    default:
                }
            }
        }
        return number.pop();
    }
//判定是否是数字
    boolean isNumber(char c)
    {
        return Character.isDigit(c);
    }
}

复杂度：

• 时间复杂度:,其中为字符串的长度，需要遍历字符串一次，计算表达式的值

• 空间复杂度：,空间复杂度主要取决于栈的空间和后缀表达式数组的大小，栈的元素个数和数组元素个数都不超过

方法二：栈+递归
相比于方法一，方法二代码会比较精简

1.先去除字符串中的空格

2.定义一个栈保存各部分表达式的和

3.遍历表达式，使用 变量记录运算符，使用 变量记录字符串中的数字部分的数字值

• 遇到数字时继续遍历求这个完整的数字的值，保存到 中
• 遇到左括号时先找到对应的右括号，因为里面可能嵌有多对括号，使用一个变量 记录括号对数直到变量为0,递归求这个括号里面的表达式的值,递归终止条件是求出最里面一层括号里表达式的值
• 遇到运算符时或者到表达式末尾时，就去计算上一个运算符并把计算结果 push进栈，然后保存新的运算符到
• 如果是 + ，直接push 进去
• 如果是 - ，push 进去负的当前数
• 如果是 ×、÷ ，pop 出一个运算数和当前数作计算

4.最后把栈中的结果求和即可

具体代码如下：

import java.util.*;

public class Solution {
    //判定是否是数字
    boolean isNumber(char c)
    {
        return Character.isDigit(c);
    }
    public int solve(String s){
        //去除字符串中的空格
        s=s.trim();
        //定义一个栈保存各部分计算出来的和
        Deque<Integer>stack=new ArrayDeque<>();
        char[]charArr=s.toCharArray();
        int num=0;
        char op='+';
        int n=charArr.length;
        for(int i=0;i<n;i++){
            char c=charArr[i];
            if(isNumber(c)){
                num=num*10+c-'0';
            }
            //递归求出括号里面表达式的值
            if(c=='('){
                int j=i+1;
                //brackets记录括号数
                int brackets=1;
                while(brackets>0){
                    if(charArr[j]=='('){
                        brackets++;
                    }
                    if(charArr[j]==')'){
                        brackets--;
                    }
                    j++;
                }
                num=solve(s.substring(i+1,j-1));
                i=j-1;
            }
            if(!isNumber(c)||i==n-1){
                if(op=='+')stack.push(num);
                else if(op=='-')stack.push(-1*num);
                else if(op=='*')stack.push(stack.pop()*num);
                else if(op=='/')stack.push(stack.pop()/num);
                num=0;
                op=c;
            }
        }
        int res=0;
        //栈中结果求和
        while(!stack.isEmpty()){
            res+=stack.pop();
        }
        return res;
    }
}

复杂度：

• 时间复杂度:,为字符串的长度，至少遍历一次字符串

• 空间复杂度：,递归深度最大为字符串长度,每次递归空间复杂度为,因此递归空间复杂度为,存储各部分计算和的栈最大不超过，所以总的空间复杂度为.