Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, 4 operators and empty spaces . The integer division should truncate toward zero.
Example 1:
Input: "3+2*2"
Output: 7
Example 2:
Input: " 3/2 "
Output: 1
Example 3:
Input: " 3+5 / 2 "
Output: 5
- Method 1:使用栈,当遇到*或/时,直接计算值再入栈。
class Solution {
public int calculate(String s) {
int len = s.length();
Stack<Integer> stack = new Stack<>();
char sign = '+';
int num = 0;
for(int i = 0; i < len; i++){
char c = s.charAt(i);
if(Character.isDigit(c))
num = num * 10 + c - '0';
if((!Character.isDigit(c) && c != ' ') || i == len - 1){
if(sign == '+')
stack.push(num);
else if(sign == '-')
stack.push(-num);
else if(sign == '*')
stack.push(num * stack.pop());
else if(sign == '/')
stack.push(stack.pop() / num);
sign = c;
num = 0;
}
}
int res = 0;
for(Integer i : stack)
res += i;
return res;
}
}
- Same idea as the first shot.
- I used a placeholder to save the previous operation
- +: put the result into stack directly.
- -: put negative value into the stack.
-
- & /: do the operation first and save the result into stack.
class Solution {
public int calculate(String s) {
int len = s.length();
char[] arr = s.toCharArray();
Stack<Integer> stack = new Stack<>();
char opt = ' ';
for(int i = 0; i < len; i++){
char c = arr[i];
if(Character.isDigit(c)){
int num = c - '0';
while(i + 1 < len && Character.isDigit(arr[i + 1])){
num = num * 10 + arr[++i] - '0';
}
if(opt == '*'){
int pre = stack.pop();
stack.push(pre * num);
}else if(opt == '/'){
int pre = stack.pop();
stack.push(pre / num);
}else if(opt == '-'){
stack.push(-1 * num);
}else{
stack.push(num);
}
}else if(c == '+' ||c == '-' ||c == '*' || c == '/'){
opt = c;
}
}
int result = 0;
for(Integer i : stack)
result += i;
return result;
}
}
- Method 1: Stack
class Solution { public int calculate(String s) { int len = s.length(); if(len == 0) return 0; char[] arr = s.toCharArray(); Stack<Integer> numbers = new Stack<>(); char operators = '+'; numbers.push(0); int index = 0; while(index < len){ char c = arr[index]; if(Character.isDigit(c)){ int temp = c - '0'; index++; while(index < len && Character.isDigit(arr[index])){ temp = temp * 10 + arr[index] - '0'; index++; } index--; if(operators == '*'){ numbers.push(temp * numbers.pop()); }else if(operators == '/'){ numbers.push(numbers.pop() / temp); }else if(operators == '-'){ numbers.push(-temp); }else numbers.push(temp); }else if(c == '+' || c == '-' || c == '*' || c == '/'){ operators = c; } index++; } int sum = 0; while(!numbers.isEmpty()){ sum += numbers.pop(); } return sum; } }