Leetcode - Calculator

[分析]
思路1：逆序遍历字符串，数字和右括号保存在一个堆栈stack1中，运算符保存在另一个堆栈stack2中，跳过空格，遇到左括号时计算stack1中首个右括号之上的所有数据，也即当前括号对中的内容。 在Accept之前有两个出错点：1）采用顺序遍历。出错case：2-1+1，因为加减的运算顺序是从左至右；2）逆序遍历时拼接完一个位数大于1的完整int 后要逆序已得到实际数值。出错case: 2147483647
思路2：参考如下两篇文章
https://leetcode.com/discuss/41868/java-solution-stack
https://leetcode.com/discuss/39479/simple-c-in-24-ms
非常不错的思路，简单来说就是将算式映射为没有括号的样子来计算

public class Solution {
    // Method 2
    public int calculate(String s) {
        if (s == null || s.equals(""))
            return 0;
        LinkedList<Integer> signs = new LinkedList<Integer>();
        signs.push(1);
        int currSign = 1;
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            int num = 0;
            while (i < s.length() && '0' <= s.charAt(i) && s.charAt(i) <= '9') {
                num = num * 10 + s.charAt(i++) - '0';
            }
            // System.out.println(sum + " " + currSign + " " + signs.peek() + " " + num);
            sum += currSign * signs.peek() * num;
            if (i == s.length()) break;
            char c = s.charAt(i);
            if (c == '+') currSign = 1;
            else if (c == '-') currSign = -1;
            else if (c == '(') {signs.push(signs.peek() * currSign); currSign = 1;}
            else if (c == ')') signs.pop();
        }
        return sum;
    }
    // Method 1
    public int calculate1(String s) {
        if (s == null || s.equals(""))
            return 0;
        LinkedList<String> nums = new LinkedList<String>();
        LinkedList<Character> ops = new LinkedList<Character>();
        int n = s.length();
        int i = n - 1;
        while (i >= 0) {
            StringBuilder num = new StringBuilder();
            while (i >= 0 && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                num.append(s.charAt(i--));
            }
            if (num.length() > 0) {
                nums.push(num.reverse().toString());
                if (i < 0) break;
            }
                
            char c = s.charAt(i);
            if (c == ')') {
                nums.push(")");
            } else if (c == '(') {
                while (!nums.peek().equals(")")) {
                    sum(nums, ops);
                }
                nums.pop();
            } else if (c == '+' || c == '-') {
                ops.push(c);
            }
            i--;
        }
        while (!ops.isEmpty()) {
            sum(nums, ops);
        }
        return !nums.isEmpty() ? Integer.valueOf(nums.pop()) : 0;
    }
    private void sum(LinkedList<String> nums, LinkedList<Character> ops) {
        int num1 = Integer.valueOf(nums.pop());
        if (nums.peek().equals(")")) {
            nums.pop();
            nums.push(String.valueOf(num1));
            nums.push(")");
            return;
        }
        int num2 = Integer.valueOf(nums.pop());
        char op = ops.pop();
        if (op == '+')
            nums.push(String.valueOf(num1 + num2));
        else
            nums.push(String.valueOf(num1 - num2));
    }
}

评论

1 楼 qb_2008 2015-06-10  

倒着遍历字符串有点别扭，成了右括号入栈，左括号出栈。不过读数字确实方便
一点。也可以用逆波兰表达式。也可以考虑加减法及时计算，这样左右括号就不必
放在操作数栈中。