LeetCode刷题—实现计算器

首先实现加减乘除运算的计算器。

题目：

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

示例 1：

输入：s = "3+2*2" 输出：7

题目要求： 1. 输入一个字符串，可以包含+ - * / 、数字、空格，你的算法返回运算结果。 2. 符合运算法则，先乘除后加减。 3. 除号是整数除法，5/2=2，-5/2=-2。

因为有运算顺序，想到用栈实现。对于第一条，遍历整个字符串，可以判断当前字符是否是数字或运算符。

思路：

建立两个变量，一个char变量，记录每个数字前的运算符。一个num变量，记录当前遍历到的数字（注意记录完整的数字）。

那么遍历字符串，如果是数字就更新num；

如果是运算符就分别讨论：

• 加/ 减：将 num/-num 压入栈
• 乘/ 除：计算数字与栈顶元素，并将栈顶元素替换为计算结果

更新num = 0，preSign = 遍历的字符

代码

class Solution {
    public int calculate(String s) {
        char[] ch = s.toCharArray();
        Stack<Integer> stack = new Stack<>();//存放每个小表达式计算的结果
        int num = 0;
        char preSign = '+';
        for(int i = 0; i < s.length(); i++){
            //如果当前遍历的字符是数字，更新num，注意要获取完整的数字
            if(ch[i] >= 48 && ch[i] <= 57){
                num = num * 10 + ch[i] - '0';
            }
            //如果不是数字也不是空格 或 已遍历到字符串的末尾，需要根据preSign得到相应结果
            if(!Character.isDigit(ch[i]) && ch[i] != ' ' || i == s.length() - 1){
                switch(preSign){
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    case '/':
                        stack.push(stack.pop() / num);
                        break;
                }
                num = 0;
                preSign = ch[i];                
            }
            
        }
        int res = 0;
        while(!stack.isEmpty()){
            res += stack.pop();
        }
        return res;
    }
}

下面就是处理括号，运算法则：有括号先算括号，即先求括号内的式子，就想到了递归。将括号内的结果作为 num，再进行后面运算。

以字符串3*(4-5/2)-6举例：

calculate(3(4-5/2)-6) = 3 calculate(4-5/2) - 6 = 3 * 2 - 6 = 0

具体实现只需要判断左右括号，如果当前遍历字符是 '('，进行递归；如果是 ')'，结束。

代码

class Solution {
    public int calculate(String s) {
        Deque<Character> q=new LinkedList<>();
        for(char c:s.toCharArray()){
            q.offer(c);
        }
        return helper(q);
    }
    public int helper(Deque<Character> q){
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        char preSign = '+';
        while(!q.isEmpty()){
            char c = q.pop();
            if(Character.isDigit(c)){
                num = num * 10 + (c - '0');
            }
            if(c == '('){
                num = helper(q);
            }
            if(!Character.isDigit(c) && c != ' ' || q.isEmpty()){              
                if(preSign=='+'){
                    stack.push(num);
                }
                else if(preSign=='-'){
                    stack.push(-num);
                }

                num = 0;
                preSign = c;               
            }
            if(c == ')') break;
        }
        int res = 0;
        while(!stack.isEmpty()){
            res += stack.pop();
        }
        return res;
    }
}