Basic Calculator II
Basic Calculator II:
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-2^31, 2^31 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = "3+2*2"
Output: 7
Example 2:
Input: s = " 3/2 "
Output: 1
Example 3:
Input: s = " 3+5 / 2 "
Output: 5
Constraints:
1 <= s.length <= 3 * 10^5sconsists of integers and operators('+', '-', '*', '/')separated by some number of spaces.srepresents a valid expression.- All the integers in the expression are non-negative integers in the range
[0, 2^31 - 1]. - The answer is guaranteed to fit in a 32-bit integer.
Try this Problem on your own or check similar problems:
Solution:
- Java
- JavaScript
- Python
- C++
public int calculate(String s) {
int num = 0, lastNum = 0, result = 0;
char operation = '+';
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = (num * 10) + (c - '0');
}
if (!Character.isDigit(c) && !Character.isWhitespace(c) || i == s.length() - 1) {
if (operation == '+') {
result += lastNum;
lastNum = num;
}
else if (operation == '-') {
result += lastNum;
lastNum = -num;
}
else if (operation == '*') {
lastNum = lastNum * num;
}
else if (operation == '/') {
lastNum = lastNum / num;
}
operation = c;
num = 0;
}
}
return result + lastNum;
}
/**
* @param {string} s
* @return {number}
*/
var calculate = function (s) {
let num = 0;
let lastNum = 0;
let result = 0;
let operation = "+";
for (let i = 0; i < s.length; ++i) {
const c = s.charAt(i);
if (isDigit(c)) {
num = num * 10 + parseInt(c);
}
if ((!isDigit(c) && !isWhitespace(c)) || i === s.length - 1) {
if (operation === "+") {
result += lastNum;
lastNum = num;
} else if (operation === "-") {
result += lastNum;
lastNum = -num;
} else if (operation === "*") {
lastNum = lastNum * num;
} else if (operation === "/") {
lastNum = round(lastNum / num);
}
operation = c;
num = 0;
}
}
return result + lastNum;
};
function isDigit(c) {
return /^\d$/.test(c);
}
function isWhitespace(c) {
return /^\s$/.test(c);
}
function round(v) {
return (v >= 0 || -1) * Math.floor(Math.abs(v));
}
class Solution:
def calculate(self, s: str) -> int:
num = 0
lastNum = 0
result = 0
operation = '+'
for i in range(len(s)):
c = s[i]
if c.isdigit():
num = num * 10 + int(c)
if (not c.isdigit() and not c.isspace()) or i == len(s) - 1:
if operation == '+':
result += lastNum
lastNum = num
elif operation == '-':
result += lastNum
lastNum = -num
elif operation == '*':
lastNum *= num
elif operation == '/':
lastNum = int(lastNum / num)
operation = c
num = 0
return result + lastNum
class Solution {
public:
int calculate(string s) {
int num = 0;
int lastNum = 0;
int result = 0;
char operation = '+';
for (int i = 0; i < s.length(); ++i) {
char c = s[i];
if (isdigit(c)) {
num = num * 10 + (c - '0');
}
if (!isdigit(c) && !isspace(c) || i == s.length() - 1) {
if (operation == '+') {
result += lastNum;
lastNum = num;
}
else if (operation == '-') {
result += lastNum;
lastNum = -num;
}
else if (operation == '*') {
lastNum *= num;
}
else if (operation == '/') {
lastNum /= num;
}
operation = c;
num = 0;
}
}
return result + lastNum;
}
};
Time/Space Complexity:
- Time Complexity: O(n)
- Space Complexity: O(1)
Explanation:
We first have to ask if we're only given valid expressions (nothing like +*5), since by the problem statement we're, we can proceed. We can use the stack as natural choice when it comes to evaluating expressions like we did in Evaluate Reverse Polish Notation. We have two scenarios either we encounter a sequence of digits, and we build the number each time shifting it by 10 and adding the new digit to the end, or we have an operation (or we traversed the whole string). We keep building the number and we keep track of the last operation (starting with +), when we encounter a new operation, we have to check what our last one was. If it was + or - we just add the number to the stack with correct sign so it can be later added/subtracted to the total sum. If we have * or / we pop the latest number and use it as first operand with the second operand being the number, we just built by traversing the string and we push the result of the operation back in the stack. We record the new operation and reset the num. Finally, we accumulate all the numbers left in the stack and return their sum as the result. Time and space complexity are proportional to the length of input string s.
- Java
- JavaScript
- Python
- C++
public int calculate(String s) {
Stack<Integer> stack = new Stack<Integer>();
int num = 0;
char operation = '+';
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = (num * 10) + (c - '0');
}
if (!Character.isDigit(c) && !Character.isWhitespace(c) || i == s.length() - 1) {
if (operation == '+') {
stack.push(num);
}
else if (operation == '-') {
stack.push(-num);
}
else if (operation == '*') {
stack.push(stack.pop() * num);
}
else if (operation == '/') {
stack.push(stack.pop() / num);
}
operation = c;
num = 0;
}
}
int result = 0;
while (!stack.isEmpty()) {
result += stack.pop();
}
return result;
}
/**
* @param {string} s
* @return {number}
*/
var calculate = function (s) {
const stack = [];
let num = 0;
let operation = "+";
for (let i = 0; i < s.length; ++i) {
const c = s.charAt(i);
if (isDigit(c)) {
num = num * 10 + parseInt(c);
}
if ((!isDigit(c) && !isWhitespace(c)) || i === s.length - 1) {
if (operation === "+") {
stack.push(num);
} else if (operation === "-") {
stack.push(-num);
} else if (operation === "*") {
stack.push(stack.pop() * num);
} else if (operation === "/") {
stack.push(Math.trunc(stack.pop() / num));
}
operation = c;
num = 0;
}
}
let result = 0;
while (stack.length > 0) {
result += stack.pop();
}
return result;
};
function isDigit(c) {
return /^\d$/.test(c);
}
function isWhitespace(c) {
return /^\s$/.test(c);
}
class Solution:
def calculate(self, s: str) -> int:
stack = []
num = 0
operation = '+'
for i in range(len(s)):
c = s[i]
if c.isdigit():
num = num * 10 + int(c)
if not c.isdigit() and not c.isspace() or i == len(s) - 1:
if operation == '+':
stack.append(num)
elif operation == '-':
stack.append(-num)
elif operation == '*':
stack.append(stack.pop() * num)
elif operation == '/':
stack.append(int(stack.pop() / num))
operation = c
num = 0
result = 0
while stack:
result += stack.pop()
return result
class Solution {
public:
int calculate(string s) {
std::stack<int> stack;
int num = 0;
char operation = '+';
for (int i = 0; i < s.length(); ++i) {
char c = s[i];
if (std::isdigit(c)) {
num = num * 10 + (c - '0');
}
if (!std::isdigit(c) && !std::isspace(c) || i == s.length() - 1) {
if (operation == '+') {
stack.push(num);
}
else if (operation == '-') {
stack.push(-num);
}
else if (operation == '*') {
stack.push(stack.top() * num);
stack.pop();
}
else if (operation == '/') {
stack.push(stack.top() / num);
stack.pop();
}
operation = c;
num = 0;
}
}
int result = 0;
while (!stack.empty()) {
result += stack.top();
stack.pop();
}
return result;
}
};
If you think about it we only need stack to hold the last number for us so we can use it as operand and to accumulate the sum of the number in the final stage, so if we accumulate early when we hit + or - operation using a result variable and also keep a reference to the last number lastNum (top of our stack) we can eliminate the need for stack and reduce the space complexity down to O(1).
- Java
- JavaScript
- Python
- C++
public int calculate(String s) {
int num = 0, lastNum = 0, result = 0;
char operation = '+';
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = (num * 10) + (c - '0');
}
if (!Character.isDigit(c) && !Character.isWhitespace(c) || i == s.length() - 1) {
if (operation == '+') {
result += lastNum;
lastNum = num;
}
else if (operation == '-') {
result += lastNum;
lastNum = -num;
}
else if (operation == '*') {
lastNum = lastNum * num;
}
else if (operation == '/') {
lastNum = lastNum / num;
}
operation = c;
num = 0;
}
}
return result + lastNum;
}
/**
* @param {string} s
* @return {number}
*/
var calculate = function (s) {
let num = 0;
let lastNum = 0;
let result = 0;
let operation = "+";
for (let i = 0; i < s.length; ++i) {
const c = s.charAt(i);
if (isDigit(c)) {
num = num * 10 + parseInt(c);
}
if ((!isDigit(c) && !isWhitespace(c)) || i === s.length - 1) {
if (operation === "+") {
result += lastNum;
lastNum = num;
} else if (operation === "-") {
result += lastNum;
lastNum = -num;
} else if (operation === "*") {
lastNum = lastNum * num;
} else if (operation === "/") {
lastNum = round(lastNum / num);
}
operation = c;
num = 0;
}
}
return result + lastNum;
};
function isDigit(c) {
return /^\d$/.test(c);
}
function isWhitespace(c) {
return /^\s$/.test(c);
}
function round(v) {
return (v >= 0 || -1) * Math.floor(Math.abs(v));
}
class Solution:
def calculate(self, s: str) -> int:
num = 0
lastNum = 0
result = 0
operation = '+'
for i in range(len(s)):
c = s[i]
if c.isdigit():
num = num * 10 + int(c)
if (not c.isdigit() and not c.isspace()) or i == len(s) - 1:
if operation == '+':
result += lastNum
lastNum = num
elif operation == '-':
result += lastNum
lastNum = -num
elif operation == '*':
lastNum *= num
elif operation == '/':
lastNum = int(lastNum / num)
operation = c
num = 0
return result + lastNum
class Solution {
public:
int calculate(string s) {
int num = 0;
int lastNum = 0;
int result = 0;
char operation = '+';
for (int i = 0; i < s.length(); ++i) {
char c = s[i];
if (isdigit(c)) {
num = num * 10 + (c - '0');
}
if (!isdigit(c) && !isspace(c) || i == s.length() - 1) {
if (operation == '+') {
result += lastNum;
lastNum = num;
}
else if (operation == '-') {
result += lastNum;
lastNum = -num;
}
else if (operation == '*') {
lastNum *= num;
}
else if (operation == '/') {
lastNum /= num;
}
operation = c;
num = 0;
}
}
return result + lastNum;
}
};