LeetCode 224. Basic Calculator

Problem:

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

Note: Do not use the eval built-in library function.

Solution:

Stack. I’ve seen this on Java intro book. Yeah my code is bad…

public class Solution {
    Stack<Integer> elements = new Stack<Integer>();
    Stack<Character> operators = new Stack<Character>();
    ArrayList<Character> op = new ArrayList<Character>();
    
    public int calculate(String s) {
        op.add('+');
        op.add('-');
        op.add('(');
        op.add(')');
        String temp = "";
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (op.indexOf(c) > -1) {
                temp = temp.trim();
                if (!temp.equals("")) {
                    elements.push(Integer.parseInt(temp));
                    temp = "";
                }
                if (c == ')') {
                    char pk = operators.pop();
                    while (pk != '(') {
                        int v1 = elements.pop();
                        int v2 = elements.pop();
                        if (pk == '+') elements.push(v1+v2);
                        else if (pk == '-') elements.push(v2-v1);
                        pk = operators.pop();
                    }
                    continue;
                }
                char pk = operators.isEmpty() ? 'e' : operators.peek();
                if (pk != 'e' && op.indexOf(pk) < 2 && c != '(') { // + or -
                    operators.pop();
                    int v1 = elements.pop();
                    int v2 = elements.pop();
                    if (pk == '+') elements.push(v1+v2);
                    else elements.push(v2-v1);
                }
                operators.push(c);
            }
            else if (i == s.length() - 1) {
                temp += c;
                temp = temp.trim();
                if (!temp.equals("")) {
                    elements.push(Integer.parseInt(temp));
                }
                char pk = operators.isEmpty() ? 'e' : operators.peek();
                if (pk != 'e' && op.indexOf(pk) < 2) { // + or -
                    operators.pop();
                    int v1 = elements.pop();
                    int v2 = elements.pop();
                    if (pk == '+') elements.push(v1+v2);
                    else elements.push(v2-v1);
                }
            }
            else {
                temp += c;
            }
        }
        while (!operators.empty()) {
            char op = operators.pop();
            int v1 = elements.pop();
            int v2 = elements.pop();
            if (op == '+') elements.push(v1+v2);
            else elements.push(v2-v1);
        }
        return elements.pop();
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *