Java one pass solution with one stack


  • 3
    D

    The idea is to use a stack to record "-" or "+" sign before a "(".

    public class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(1);
        int sign = 1;
        int start = 0;
        long rst = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '+') {
                sign = 1;
            } else if (s.charAt(i) == '-') {
                sign = -1;
            } else if (s.charAt(i) == '(') {
                stack.push(sign * stack.peek());
                sign = 1;
            } else if (s.charAt(i) == ')') {
                stack.pop();
            }
            if (isDigit(s, i) && (i == 0 || !isDigit(s, i - 1))) {
                start = i;
            }
            if (isDigit(s, i) && (i == s.length() - 1 || !isDigit(s, i + 1))) {
                // find a number
                long num = Long.parseLong(s.substring(start, i + 1));
                num = num * sign * stack.peek();
                rst += num;
            }
        }
        return (int)rst;
    }
    boolean isDigit(String s, int i) {
        return s.charAt(i) >= '0' && s.charAt(i) <= '9';
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.