LeetCode 227 - Basic Calculator II
LeetCode – Basic Calculator (Java)
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, "(1)" = 1, "(1-(4-5))" = 2
1. Use stack: opStack && numStack
CHECK this: https://github.com/eryueniaobp/leetcode/blob/master/string%20algorithm/Calculator.cpp
X. Using one stack
https://www.cnblogs.com/grandyang/p/4570699.html
这道题让我们实现一个基本的计算器来计算简单的算数表达式，而且题目限制了表达式中只有加减号，数字，括号和空格，没有乘除，那么就没啥计算的优先级之分了。于是这道题就变的没有那么复杂了。我们需要一个栈来辅助计算，用个变量sign来表示当前的符号，我们遍历给定的字符串s，如果遇到了数字，由于可能是个多位数，所以我们要用while循环把之后的数字都读进来，然后用sign*num来更新结果res；如果遇到了加号，则sign赋为1，如果遇到了符号，则赋为-1；如果遇到了左括号，则把当前结果res和符号sign压入栈，res重置为0，sign重置为1；如果遇到了右括号，结果res乘以栈顶的符号，栈顶元素出栈，结果res加上栈顶的数字，栈顶元素出栈
https://discuss.leetcode.com/topic/33044/java-easy-version-to-understand
https://discuss.leetcode.com/topic/15816/iterative-java-solution-with-stack
我们需要一个栈来辅助计算，用个变量sign来表示当前的符号，我们遍历给定的字符串s，如果遇到了数字，由于可能是个多位数，所以我们要用while循环把之后的数字都读进来，然后用sign*num来更新结果res；如果遇到了加号，则sign赋为1，如果遇到了符号，则赋为-1；如果遇到了左括号，则把当前结果res和符号sign压入栈，res重置为0，sign重置为1；如果遇到了右括号，结果res乘以栈顶的符号，栈顶元素出栈，结果res加上栈顶的数字，栈顶元素出栈
http://www.wengweitao.com/leetcode-basic-calculator.html
如果当前字符c是数字字符，数字可能不止一位，所以需要继续遍历下一个字符，若仍然是数字字符，将其与前面的连续数字字符组成一个数num，直到遇到下一个非数字字符；
如果当前的字符c是'+'，那么就将前面的num加到result中，并且设置符号标记sign=1为正；
如果当前字符c是'-'，那么就用result - num，并且设置符号标记sign=-1为负；
如果当前字符c是'('，那么先保存当前的result和符号sign到栈中，再继续计算括号里面的表达式；
如果当前字符c是')'，那么计算完毕当前括号的result后，依次弹出栈顶的sign和result，然后将括号中的result和栈顶弹出的result相加（或相减，由sign决定）；
继续以上步骤，直到遍历到字符串的最后一个字符
下面这种方法和上面的基本一样，只不过对于数字的处理略微不同，上面的方法是连续读入数字，而这种方法是使用了一个变量来保存读入的num，所以在遇到其他字符的时候，都要用sign*num来更新结果res
http://shibaili.blogspot.com/2015/06/day-112-count-complete-tree-nodes.html
用初始化 sign = 1来处理符号，能解决特殊情况. 对()的处理
http://www.cnblogs.com/tonix/p/4563300.html
X. Only use stack to store the sign info (1 or -1) when meet ‘(‘ or ‘)’
这道题让我们实现一个基本的计算器来计算简单的算数表达式，而且题目限制了表达式中只有加减号，数字，括号和空格，没有乘除，那么就没啥计算的优先级之分了。于是这道题就变的没有那么复杂了。我们需要一个一维的符号数组来记录加减号，然后我们开始遍历字符串表达式，如果遇到的是数字，则从符号数组中取出最后一个符合和数字运算后更新结果，如果遇到右括号，则移除一个符号，如果遇到的不是空格，即有可能是加减号或是左括号，则符号数组中加1或-1，做个判断，如果是负号，加个-1，其他情况加1。代码如下：
X. Using tow stacks
http://buttercola.blogspot.com/2015/08/leetcode-basic-calculator.html
1. If num, push into num stack.
2. If operator:
-- If the op stack is empty, push the operator into the stack.
-- If the op has higher precedence, e.g. * or /, check the top of the op stack.
-- If the top operator on the op stack is a "(", push and move on.
-- If the top operator on the op stack has lowe precedence as well, push into the stack.
-- If the top operator on the op stack has the same precedence, consume one operation, and then push the op into the op stack.
-- If the op has lower percedence, e.g. + or -, check the top of the op stack as well.
-- If the top of the op stack is a left parthesis, push the op and move on
-- Else, Pop one operator and two operands from the two stacks, resp. and push the result back.
-- If the op is a left parthesis, push to the op stack and move on.
-- If the op is a right parthesis, pop and compuate until we reach a left parthesis.
The problem looks complicated to implement, actually could be memorized in a template way.
If the token is a number, then push it to the num stack.
If the token is a operator, there are 5 cases to consider:
1. If the opStack is empty
-- push into opStack
2. If the token is + or -
-- Check the top of the opStack.
-- If the top is '(', then push the token into opStack.
-- Else (which means has higher or equal precedence), consume the stack by doing one computation.
3. If the token is * or /
-- If the top is '(', push the token into opStack
-- Else if top has lower precedence ( + or -), push the token into opStack.
-- Else if the top has equal precedence (* or /), consume the stack by doing one computation.
4. If the token is (
-- Push into opStack
5. If the token is )
-- Doing computations until we see the '(' in the opStack.
There is another corner case need to be very careful is:
If the input String has only one number, e.g. (1), 1, 1*. For OA it is still valid. So the trick to handle this edge case is in the computation method, before we pop two numbers from the numStack, we check if the size of the numStack. If less than 2, we know that this case happens. Then we only need to do is pop out the opStack until it is empty. Then the result is the only number in the numStack.
X. Recursion
https://www.cnblogs.com/grandyang/p/4570699.html
在做了Basic Calculator III之后，再反过头来看这道题，发现递归处理括号的方法在这道题也同样适用，我们用一个变量cnt，遇到左括号自增1，遇到右括号自减1，当cnt为0的时候，说明括号正好完全匹配，这个trick在验证括号是否valid的时候经常使用到。然后我们就是根据左右括号的位置提取出中间的子字符串调用递归函数，返回值赋给num
http://codechen.blogspot.com/2015/06/leetcode-basic-calculator.html
http://yuanhsh.iteye.com/blog/2194524
LeetCode – Basic Calculator (Java)
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, "(1)" = 1, "(1-(4-5))" = 2
1. Use stack: opStack && numStack
CHECK this: https://github.com/eryueniaobp/leetcode/blob/master/string%20algorithm/Calculator.cpp
X. Using one stack
https://www.cnblogs.com/grandyang/p/4570699.html
这道题让我们实现一个基本的计算器来计算简单的算数表达式，而且题目限制了表达式中只有加减号，数字，括号和空格，没有乘除，那么就没啥计算的优先级之分了。于是这道题就变的没有那么复杂了。我们需要一个栈来辅助计算，用个变量sign来表示当前的符号，我们遍历给定的字符串s，如果遇到了数字，由于可能是个多位数，所以我们要用while循环把之后的数字都读进来，然后用sign*num来更新结果res；如果遇到了加号，则sign赋为1，如果遇到了符号，则赋为-1；如果遇到了左括号，则把当前结果res和符号sign压入栈，res重置为0，sign重置为1；如果遇到了右括号，结果res乘以栈顶的符号，栈顶元素出栈，结果res加上栈顶的数字，栈顶元素出栈
https://discuss.leetcode.com/topic/33044/java-easy-version-to-understand
https://discuss.leetcode.com/topic/15816/iterative-java-solution-with-stack
Simple iterative solution by identifying characters one by one. One important thing is that the input is valid, which means the parentheses are always paired and in order.
Only 5 possible input we need to pay attention:
Only 5 possible input we need to pay attention:
- digit: it should be one digit from the current number
- '+': number is over, we can add the previous number and start a new number
- '-': same as above
- '(': push the previous result and the sign into the stack, set result to 0, just calculate the new result within the parenthesis.
- ')': pop out the top two numbers from stack, first one is the sign before this pair of parenthesis, second is the temporary result before this pair of parenthesis. We add them together.
Finally if there is only one number, from the above solution, we haven't add the number to the result, so we do a check see if the number is zero.
public int calculate(String s) {
Stack<Integer> stack = new Stack<Integer>();
int result = 0;
int number = 0;
int sign = 1;
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(Character.isDigit(c)){
number = 10 * number + (int)(c - '0');
}else if(c == '+'){
result += sign * number;
number = 0;
sign = 1;
}else if(c == '-'){
result += sign * number;
number = 0;
sign = -1;
}else if(c == '('){
//we push the result first, then sign;
stack.push(result);
stack.push(sign);
//reset the sign and result for the value in the parenthesis
sign = 1;
result = 0;
}else if(c == ')'){
result += sign * number;
number = 0;
result *= stack.pop(); //stack.pop() is the sign before the parenthesis
result += stack.pop(); //stack.pop() now is the result calculated before the parenthesis
}
}
if(number != 0) result += sign * number;
return result;
}我们需要一个栈来辅助计算，用个变量sign来表示当前的符号，我们遍历给定的字符串s，如果遇到了数字，由于可能是个多位数，所以我们要用while循环把之后的数字都读进来，然后用sign*num来更新结果res；如果遇到了加号，则sign赋为1，如果遇到了符号，则赋为-1；如果遇到了左括号，则把当前结果res和符号sign压入栈，res重置为0，sign重置为1；如果遇到了右括号，结果res乘以栈顶的符号，栈顶元素出栈，结果res加上栈顶的数字，栈顶元素出栈
http://www.wengweitao.com/leetcode-basic-calculator.html
如果当前字符c是数字字符，数字可能不止一位，所以需要继续遍历下一个字符，若仍然是数字字符，将其与前面的连续数字字符组成一个数num，直到遇到下一个非数字字符；
如果当前的字符c是'+'，那么就将前面的num加到result中，并且设置符号标记sign=1为正；
如果当前字符c是'-'，那么就用result - num，并且设置符号标记sign=-1为负；
如果当前字符c是'('，那么先保存当前的result和符号sign到栈中，再继续计算括号里面的表达式；
如果当前字符c是')'，那么计算完毕当前括号的result后，依次弹出栈顶的sign和result，然后将括号中的result和栈顶弹出的result相加（或相减，由sign决定）；
继续以上步骤，直到遍历到字符串的最后一个字符
下面这种方法和上面的基本一样，只不过对于数字的处理略微不同，上面的方法是连续读入数字，而这种方法是使用了一个变量来保存读入的num，所以在遇到其他字符的时候，都要用sign*num来更新结果res
http://shibaili.blogspot.com/2015/06/day-112-count-complete-tree-nodes.html
用初始化 sign = 1来处理符号，能解决特殊情况. 对()的处理
int calculate(string s) { stack<int> st; int sign = 1; int rt = 0; int num = 0; for (int i = 0; i < s.length(); i++) { if (isdigit(s[i])) { num = num * 10 + s[i] - '0'; }else if (s[i] == '+') { rt += sign * num; sign = 1; num = 0; }else if (s[i] == '-') { rt += sign * num; sign = -1; num = 0; }else if (s[i] == '(') { st.push(rt); st.push(sign); sign = 1; rt = 0; }else if (s[i] == ')') { rt += num * sign; sign = st.top(); st.pop(); rt = sign * rt + st.top(); st.pop(); num = 0; } } if (num != 0) { return rt + sign * num; } return rt; }这道题让我们实现一个基本的计算器来计算简单的算数表达式，而且题目限制了表达式中只有加减号，数字，括号和空格，没有乘除，那么就没啥计算的优先级之分了。于是这道题就变的没有那么复杂了。我们需要一个一维的符号数组来记录加减号，然后我们开始遍历字符串表达式，如果遇到的是数字，则从符号数组中取出最后一个符合和数字运算后更新结果，如果遇到右括号，则移除一个符号，如果遇到的不是空格，即有可能是加减号或是左括号，则符号数组中加1或-1，做个判断，如果是负号，加个-1，其他情况加1。代码如下：
public int calculate2(String s) {
Stack<Integer> stack = new Stack<Integer>();
stack.push(1);
int res = 0;
int sign = 1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '+' || c == '-') {
sign = c == '+' ? 1: -1;
} else if (c == '(') {
stack.push(sign * stack.peek());
sign = 1;
} else if (c == ')') {
sign = stack.pop();
} else if (Character.isDigit(c)) {
int num = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
i++;
}
i--;
res += sign * num * stack.peek();
}
}
return res;
}
https://leijiangcoding.wordpress.com/2015/06/08/leetcode-q224-basic-calculator/ public int calculate(String s) { Stack<Integer> numbers = new Stack<Integer>(); int num = 0, res = 0, sign = 1; for (int i = 0; i < s.length(); i++){ if (Character.isDigit(s.charAt(i))){ num = num * 10 + s.charAt(i) - '0'; }else if (s.charAt(i) == '+' || s.charAt(i) == '-'){ res += num * sign; sign = (s.charAt(i) == '+') ? 1 : -1; num = 0;//reset }else if (s.charAt(i) == '('){ //push the result to the stack numbers.push(res); numbers.push(sign); res = 0;//reset sign = 1;//reset }else if (s.charAt(i) == ')') { //remove () and pop the pre-result from the stack res += num * sign; res *= numbers.pop(); res += numbers.pop(); num = 0;//reset } } if (num != 0) res += num * sign; return res; }http://buttercola.blogspot.com/2015/08/leetcode-basic-calculator.html
1. If num, push into num stack.
2. If operator:
-- If the op stack is empty, push the operator into the stack.
-- If the op has higher precedence, e.g. * or /, check the top of the op stack.
-- If the top operator on the op stack is a "(", push and move on.
-- If the top operator on the op stack has lowe precedence as well, push into the stack.
-- If the top operator on the op stack has the same precedence, consume one operation, and then push the op into the op stack.
-- If the op has lower percedence, e.g. + or -, check the top of the op stack as well.
-- If the top of the op stack is a left parthesis, push the op and move on
-- Else, Pop one operator and two operands from the two stacks, resp. and push the result back.
-- If the op is a left parthesis, push to the op stack and move on.
-- If the op is a right parthesis, pop and compuate until we reach a left parthesis.
The problem looks complicated to implement, actually could be memorized in a template way.
If the token is a number, then push it to the num stack.
If the token is a operator, there are 5 cases to consider:
1. If the opStack is empty
-- push into opStack
2. If the token is + or -
-- Check the top of the opStack.
-- If the top is '(', then push the token into opStack.
-- Else (which means has higher or equal precedence), consume the stack by doing one computation.
3. If the token is * or /
-- If the top is '(', push the token into opStack
-- Else if top has lower precedence ( + or -), push the token into opStack.
-- Else if the top has equal precedence (* or /), consume the stack by doing one computation.
4. If the token is (
-- Push into opStack
5. If the token is )
-- Doing computations until we see the '(' in the opStack.
There is another corner case need to be very careful is:
If the input String has only one number, e.g. (1), 1, 1*. For OA it is still valid. So the trick to handle this edge case is in the computation method, before we pop two numbers from the numStack, we check if the size of the numStack. If less than 2, we know that this case happens. Then we only need to do is pop out the opStack until it is empty. Then the result is the only number in the numStack.
public int calculate(String s) { if (s == null || s.length() == 0) { return 0; } // parse the string String delim = "[ ]+"; s = s.replaceAll(delim, ""); Stack<Integer> numStack = new Stack<Integer>(); Stack<Character> opStack = new Stack<Character>(); for (int i = 0; i < s.length(); i++) { char elem = s.charAt(i); if (Character.isDigit(elem)) { // To number int num = elem - '0'; int j = i + 1; while (j < s.length() && Character.isDigit(s.charAt(j))) { num = num * 10 + (s.charAt(j) - '0'); j++; } numStack.push(num); i = j - 1; } else { // Operator if (opStack.isEmpty()) { opStack.push(elem); } else if (elem == '*' || elem == '/') { char top = opStack.peek(); if (top == '(') { opStack.push(elem); } else if (top == '+' || top == '-') { opStack.push(elem); } else { compute(numStack, opStack); opStack.push(elem); } } else if (elem == '+' || elem == '-') { char top = opStack.peek(); if (top == '(') { opStack.push(elem); } else { compute(numStack, opStack); opStack.push(elem); } } else if (elem == '(') { opStack.push(elem); } else if (elem == ')') { // Right ")" while ((!opStack.isEmpty()) && (opStack.peek() != '(')) { compute(numStack, opStack); } opStack.pop(); } } } while (!opStack.isEmpty()) { compute(numStack, opStack); } return numStack.pop(); } private void compute(Stack<Integer> numStack, Stack<Character> opStack) { if (numStack.size() < 2) { while (!opStack.isEmpty()) { opStack.pop(); } return; } int num2 = numStack.pop(); int num1 = numStack.pop(); char op = opStack.pop(); int ans = 0; switch(op) { case '+': ans = num1 + num2; break; case '-': ans = num1 - num2; break; case '*': ans = num1 * num2; break; case '/': ans = num1 / num2; break; } numStack.push(ans); }https://www.cnblogs.com/grandyang/p/4570699.html
在做了Basic Calculator III之后，再反过头来看这道题，发现递归处理括号的方法在这道题也同样适用，我们用一个变量cnt，遇到左括号自增1，遇到右括号自减1，当cnt为0的时候，说明括号正好完全匹配，这个trick在验证括号是否valid的时候经常使用到。然后我们就是根据左右括号的位置提取出中间的子字符串调用递归函数，返回值赋给num
int calculate(string s) { int res = 0, num = 0, sign = 1, n = s.size(); for (int i = 0; i < n; ++i) { char c = s[i]; if (c >= '0' && c <= '9') { num = 10 * num + (c - '0'); } else if (c == '(') { int j = i, cnt = 0; for (; i < n; ++i) { if (s[i] == '(') ++cnt; if (s[i] == ')') --cnt; if (cnt == 0) break; } num = calculate(s.substr(j + 1, i - j - 1)); } if (c == '+' || c == '-' || i == n - 1) { res += sign * num; num = 0; sign = (c == '+') ? 1 : -1; } } return res; }X. 思路：1. 可以先中缀表达式转为后缀表达式，然后求解之。
http://codechen.blogspot.com/2015/06/leetcode-basic-calculator.html
void infixToPostfix(string s, vector<string> &output){ vector<char> stack; for (int i = 0; i < s.size(); ++i) { string res; while (i <s.size()&& s[i] >= '0' && s[i] <= '9') res += s[i++]; if (res.size() != 0) output.push_back(res); if (s[i] == '(') stack.push_back(s[i]); else if (s[i] == ')') { while (!stack.empty() && stack.back() != '(') { string t(1,stack.back()); output.push_back(t); stack.pop_back(); } stack.pop_back(); } else if (s[i]=='+' || s[i]=='-') {//"+", "-" while (!stack.empty()&& stack.back() != '(') { string t (1,stack.back()); output.push_back (t); stack.pop_back (); } stack.push_back(s[i]); } } while(!stack.empty()){ string t(1,stack.back()); output.push_back(t); stack.pop_back(); } } int evalRPN(vector<string> &tokens) { vector<int> stack; for(int i = 0; i < tokens.size(); ++i){ if ( tokens[i].size() > 1 || ( tokens[i][0] >= '0' && tokens[i][0] <= '9' ) ){ stack.push_back(stoi(tokens[i])); continue; } int number1 = stack.back(); stack.pop_back(); int number2 = stack.back(); stack.pop_back(); switch(tokens[i][0]) { case '+': number2 += number1; break; case '-': number2 -= number1; break; default: break; } stack.push_back(number2); } return stack.back(); } int calculate(string s) { vector<string> postfixExpression; infixToPostfix (s, postfixExpression); return evalRPN (postfixExpression); }http://yuanhsh.iteye.com/blog/2194524
题目就是计算表达式 1+2*3+4 = 11可以去搜parse mathematical expression,不考虑括号
Solution:
use two arrays to store numbers and signs.
nums = [1,2,3,4]
signs = [+, *, +]
scan signs, when we meet * or /, and change * or / into +, corresponding nums changed to [0, a*b] or [0, a/b]. for the example:
nums = [1,0,6,4]
signs = [+,+,+].
then do (zigzag) sum.
signs = [+, *, +]
scan signs, when we meet * or /, and change * or / into +, corresponding nums changed to [0, a*b] or [0, a/b]. for the example:
nums = [1,0,6,4]
signs = [+,+,+].
then do (zigzag) sum.
- public int calcExpression(String expr) {
- //正则表达式，运算符得escape，并且用[]包裹，表示或;否则会表示"+-*/"四个都匹配才行
- String[] digits = expr.split("[\\+\\-\\*\\/]");
- //[, +, *, -, /], 第一个是leading empty string, trailing empty string会自动去掉，而头部的不会
- String[] ops = expr.split("\\d+"); // 或者下面这种做法，移除第一个数字
- // String[] ops = expr.replaceFirst("\\d+", "").split("\\d+");
- int n = digits.length;
- int[] nums = new int[n];
- for(int i=0; i<n; i++) {
- nums[i] = Integer.valueOf(digits[i]);
- }
- for(int i=1; i<ops.length; i++) {//因为第0项是空字符串，所以从第一项开始
- if(ops[i].equals("*")) {
- nums[i] = nums[i-1] * nums[i];
- nums[i-1] = 0;
- } else if(ops[i].equals("/")) {
- nums[i] = nums[i-1] / nums[i];
- nums[i-1] = 0;
- } else if(ops[i].equals("-")) {
- //不能减，因为后面有可能是*/运算，比-的优先度高，所以要变成负数的加法，这样不影响优先级
- nums[i] = -nums[i];
- }
- }
- int sum = 0;
- for(int i=0; i<n; i++) {
- sum += nums[i];
- }
- return sum;
- }
