BM49 题解 | #表达式求值#

解题思路：

我是彻底弄懂了！！！！good job！👍👍

主要是使用：栈 + 递归，来实现计算功能。

具体步骤：

1、栈： 栈stack来保存要计算的num，和，遇到*号后，立刻相乘的到结果。

2、递归： 处理”（）”，计算括号内返回的值，赋给当前递归层的num，保存起来供下次处理。

3、最后，对所有stack的num的进行求和，返回最终的结果。

注意事项，如下，注视说明。

import java.util.*;


public class Solution {
    /**
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        ArrayList<Integer> res = function(s, 0);
        return res.get(0);
    }
    
    /**
     * 递归，计算表达式求值，
     * @param s string字符串 待计算的表达式
     * @param index 上一层迭代处理s的开始位置
     * @return int整型
     */
    ArrayList<Integer> function(String s, int index) {
        Stack<Integer> stack = new Stack<>();
        int num =0;
        char op = '+';
        int i; //这里i从for(int i)提取出来方便，后面递归调用

        // 一个for循环只处理一个成对 “(” “)”括号的计算
        for(i=index; i<s.length(); i++) {
            char cs = s.charAt(i);
            // 转化数字，使用 num = num*10 + cs - '0'
            if(cs >= '0' && cs <='9')  {
                num = num *10 + cs - '0';
                if(i!=s.length()-1) {
                    continue; // 遇到数字直接进入下个char的获取
                }
            }
            // 遇到'(' 就进行递归操作，每个结果都保存到num里面，供上一层递归使用
            if(cs == '(') {
                ArrayList<Integer> fRes = function(s, i+1);
                num += fRes.get(0); //是num += .. 而非 sum += fRes.get(0); 
                i = fRes.get(1);
                if(i != s.length()-1){
                    continue; //这里其实是跟上面的取num是一样的逻辑的。
                }
            }
            // 根据op做相应的压栈和相乘操作
            switch(op) {
                case '+':
                    stack.push(num);
                    break;
                case '-':
                    stack.push(-num);
                    break;
                case '*':
                    int temp = stack.pop(); //这里被我写错pop导致整个结果错误
                    stack.push(temp * num);
                    break;
            }
            // 这里置0是对的，在op号push num进堆后，就要进行下一轮获取数字了
            num = 0; //为什么num=0；放这里，前一点后一点有什么区别？
            if(cs == ')') {
                break;
            } else {
                op = cs;
            }
        }
        // 计算所有num结果值
        int sum = 0;
        while(!stack.isEmpty()) {
            sum += stack.pop();
        }
        //返回此轮递归的结果值和下一轮计算的起始index
        ArrayList<Integer> res = new ArrayList<>();
        res.add(sum);
        res.add(i);
        return res;
    }
}