LeetCode-224.Basic Calculator
题目
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 .
样例
Input: "1 + 1" Output: 2 Input: " 2-1 + 2 " Output: 3 Input: "(1+(4+5+2)-3)+(6+8)" Output: 23
题目分析
难度: Hard
(其实是个水题)
题意
实现一个简单计算器,给出的表达式只包含+ - ( )
和空格
。两个数/运算符之间可能有空格,也可能没有空格。
非常经典的简单问题,但对于没有接触过的人来说,还是有一定难度的,难点在于括号处理和数字、运算符、括号的解析。
思路
表达式解析
因为空格出现的位置不确定,不如直接将所有空格去掉。
假设我们现在只需要处理没有括号的情况。
我们用一个index
不断在表达式中前进。用一个变量nowVal
记录数字之和。若当前为符号,则将符号记录下来。若当前为数字,则不断向后查找相连的所有数字,找出这段数字的区间,解析它。解析出数字后,若之前的符号为+
,则将数字加到nowVal
上,反之减去。
括号处理
遇到括号时,我们需要先计算出括号中所有数字的和。遇到左括号时,我们可以将当前的nowVal
和括号前的运算符压到栈中去。然后清空nowVal
,开始计算括号中的值和遇到右括号时,我们已得到了所有信息:整个括号左侧的数(在栈顶),括号左侧的运算符(在栈顶),括号的值(nowVal)。
这时将两数求值即可。
代码
import java.util.Stack; class Solution { private static final int ADD = -1; private static final int SUBTRACT = -2; private static final int LEFT = -3; private static final int RIGHT = -4; private String str; private int index = 0; public int calculate(String s) { str = s.replaceAll(" ", ""); Stack<Integer> numStk = new Stack<>(); Stack<Integer> operStk = new Stack<>(); int nowVal = 0; int last = ADD; while (hasNext()) { int now = getNext(); if (now == ADD) { last = ADD; } else if (now == SUBTRACT) { last = SUBTRACT; } else if (now == LEFT) { numStk.push(nowVal); operStk.push(last); last = ADD; nowVal = 0; } else if (now == RIGHT) { if (operStk.pop() == ADD) { nowVal = numStk.pop() + nowVal; } else { nowVal = numStk.pop() - nowVal; } } else { if (last == ADD) { nowVal += now; } else { nowVal -= now; } } } return nowVal; } private boolean hasNext() { return index < str.length(); } private int getNext() { int chr = str.charAt(index++); if (chr == '(') { return LEFT; } else if (chr == ')') { return RIGHT; } else if (chr == '+') { return ADD; } else if (chr == '-') { return SUBTRACT; } int startIndex = index - 1; while (index < str.length() && str.charAt(index) >= '0' && str.charAt(index) <= '9') { index++; } return Integer.parseInt(str.substring(startIndex, index)); } }