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(); } }