224. Basic Calculator.md

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

tag:

• stack
• suffix expression

Solution

通用解法

中缀表达式转换为后缀表达式（逆波兰表达式）， 利用后缀表达式求值 参考： http://www.cnblogs.com/zghaobac/p/3394705.html http://www.cnblogs.com/dolphin0520/p/3708602.html

易于理解的解法

由于只包含加减运算符，可把运算符当作正负符号，从左到右扫描表达式求值 如果遇到（，则把当前运算结果与运算符入栈， 如果遇到右括号，把括号中的计算结果与栈中的记过相加 java

	public int calculate(String s) {
		int sign = 1, res = 0, len = s.length();
		Stack<Integer> stack = new Stack<Integer>();
		for (int i = 0; i < len; i++) {
			if (Character.isDigit(s.charAt(i))) {
				int sum = s.charAt(i) - '0';
				while (i + 1 < len && Character.isDigit(s.charAt(i + 1))) {
					sum = sum * 10 + s.charAt(i + 1) - '0';
					i++;
				}
				res += sum*sign;
			} else if (s.charAt(i) == '+') {
				sign = 1;
			} else if (s.charAt(i) == '-') {
				sign = -1;
			} else if (s.charAt(i) == '(') {
				stack.push(res);
				stack.push(sign);
				res = 0;
				sign = 1;
			} else if (s.charAt(i) == ')') {
				res = res * stack.pop() + stack.pop();
			}
		}
		return res;
	}

go