Basic Calculator

https://leetcode.com/problems/basic-calculator/ https://leetcode.com/problems/basic-calculator-ii/

Problem description

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples: "1 + 1" = 2 " 2-1 + 2 " = 3 "(1+(4+5+2)-3)+(6+8)" = 23

Tag: Stack

public static int calculate(String s) {
    Stack<String> stack = new Stack<String>();
    for (int i = 0; i < s.length(); i++) {
        // get the number
        if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
            int j = i + 1;
            while (j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9') {
                j++;
                continue;
            }
            stack.push(s.substring(i, j));
            // since i++ in the for loop
            i = j - 1;
        } else if (s.charAt(i) == '+' || s.charAt(i) == ('-') || s.charAt(i) == '(') {
            stack.push(s.substring(i, i + 1));
        } else if (s.charAt(i) == ')') {
            // start to calculate
            List<String> expr = new ArrayList<String>();
            // pop the stack until meet the open (
            while (!stack.isEmpty()) {
                String e = stack.pop();
                if (e.equals("(")) {
                    break;
                } else {
                    expr.add(e);
                }

            }
            // we want to calculate from left to right
            Collections.reverse(expr);
            stack.push(String.valueOf(calculateStringExpr(expr)));
        }
    }

    if (stack.size() == 1) {
        return Integer.valueOf(stack.pop());
    } else {
        List<String> expr = new ArrayList<String>();
        while (!stack.isEmpty()) {
            expr.add(stack.pop());
        }
        Collections.reverse(expr);

        return calculateStringExpr(expr);
    }
}

// this helper function calculate an expression without parenthesis 
private static int calculateStringExpr(List<String> list) {
    if (list.size() == 1) {
        return Integer.valueOf(list.get(0));
    } else {
        int result = Integer.valueOf(list.get(0));
        for (int i = 1; i < list.size(); i = i + 2) {
            if (list.get(i).equals("+")) {
                result += Integer.valueOf(list.get(i + 1));
            } else {
                result -= Integer.valueOf(list.get(i+1));
            }
        }
        return result;
    }
}

Follow up:

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples: "3+2*2" = 7 " 3/2 " = 1 " 3+5 / 2 " = 5

solution

Since there is no parentheses, every time we encounter '*' and '\', we can just start to evaluate.

public static int calculate2(String s) {
    boolean existOperator = false;
    Stack<String> stack = new Stack<String>();

    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
            int j = i + 1;
            while (j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9') {
                j++;
            }
            // if * / operator appeared before
            if (existOperator) {
                String result;
                String operator = stack.pop();
                if (operator.equals("*")) {
                    result = String.valueOf(Integer.valueOf(stack.pop()) * Integer.valueOf(s.substring(i, j)));
                } else {
                    result = String.valueOf(Integer.valueOf(stack.pop()) / Integer.valueOf(s.substring(i, j)));
                }
                stack.push(result);
                existOperator = false;
            } else {
                stack.push(s.substring(i, j));
            }
            i = j - 1;
        } else {
            switch (s.charAt(i)) {
                case '*': case '/':
                    stack.push(s.substring(i, i + 1));
                    existOperator = true;
                    break;
                case '+':case '-':
                    stack.push(s.substring(i, i + 1));
            }
        }
    }

    if (stack.size() == 1) {
        return Integer.valueOf(stack.pop());
    } else {
        List<String> expr = new ArrayList<String>();
        while (!stack.isEmpty()) {
            expr.add(stack.pop());
        }
        Collections.reverse(expr);

        int result = Integer.valueOf(expr.get(0));
        for (int i = 1; i < expr.size(); i = i + 2) {
            String operator = expr.get(i);
            if (operator.equals("+")) {
                result += Integer.valueOf(expr.get(i+1));
            } else {
                result -= Integer.valueOf(expr.get(i+1));
            }

        }
        return result;
    }
}