Algorithm
Problem Name: 224. Basic Calculator
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = "1 + 1" Output: 2
Example 2:
Input: s = " 2-1 + 2 " Output: 3
Example 3:
Input: s = "(1+(4+5+2)-3)+(6+8)" Output: 23
Constraints:
1 <= s.length <= 3 * 105sconsists of digits,'+','-','(',')', and' '.srepresents a valid expression.'+'is not used as a unary operation (i.e.,"+1"and"+(2 + 3)"is invalid).'-'could be used as a unary operation (i.e.,"-1"and"-(2 + 3)"is valid).- There will be no two consecutive operators in the input.
- Every number and running calculation will fit in a signed 32-bit integer.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
int *p;
int sz;
int n;
} s_t;
int parse(char **sp, int *k) {
char *s = *sp;
while (*s == ' ') s ++;
*k = 0;
if (*s == 0) return 0;
if (*s == '+' || *s == '-' || *s == '*' || *s == '/' || *s == '(' || *s == ')') {
*k = *s == '+' ? 1 :
*s == '-' ? 2 :
*s == '*' ? 3 :
*s == '/' ? 4 :
*s == '(' ? 5 : 6;
*sp = ++ s;
return 1;
}
while (*s >= '0' && *s < = '9') {
*k = (*k) * 10 + *s - '0';
s ++;
}
*sp = s;
return 2;
}
void push(s_t *stack, int k) {
if (stack->sz == stack->n) {
stack->sz *= 2;
stack->p = realloc(stack->p, stack->sz * sizeof(int));
//assert(stack->p);
}
stack->p[stack->n ++] = k;
}
int low_op(s_t *ops, int k) {
const int priority[] = { 0, 2, 2, 3, 3, 1, 1 }; // null, +, -, *, /, (, )
return (priority[ops->p[ops->n - 1]] >= priority[k]) ? 1 : 0;
}
int calculate(char* s) {
s_t data = { 0 }, ops = { 0 };
int x, k, d1, d2, o;
data.n = ops.n = 0;
data.sz = ops.sz = 10;
data.p = malloc(data.sz * sizeof(int));
ops.p = malloc(ops.sz * sizeof(int));
push(&data, 0); // put a zero in case of with a null input
push(&ops, 0); // put a null operator on top of operator stack
do {
x = parse(&s, &k);
if (x == 2) { // data, push to stack
push(&data, k);
} else if (k == 5) { // left parenthese, always push
push(&ops, k);
} else { // operator
while (low_op(&ops, k)) {
o = ops.p[-- ops.n];
if (o == 0 || o == 5) break; // end of input or left parenthese
d2 = data.p[-- data.n];
d1 = data.p[-- data.n];
switch (o) {
case 1: // '+'
d1 = d1 + d2;
break;
case 2: // '-'
d1 = d1 - d2;
break;
case 3: // '*'
d1 = d1 * d2;
break;
case 4: // '/'
d1 = d1 / d2;
break;
default:
break;
}
push(&data, d1);
}
if (k && k != 6) push(&ops, k); // ignore end or right parenthese
}
} while (x);
//assert(ops.n == 0);
k = data.p[data.n - 1];
free(data.p);
free(ops.p);
return k;
}
Input
s = "1 + 1"
Output
2
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int calculate(string s) {
stack<int>stk, op;
int res = 0, sign = 1;
for(int i = 0; i < s.size(); i++){
char c = s[i];
if(isdigit(c)){
int num = c - '0';
while(i + 1 < s.size() && isdigit(s[i + 1])){
num = num * 10 + s[i + 1] - '0';
i++;
}
res += num * sign;
}
else if(c == '+') sign = 1;
else if(c == '-') sign = -1;
else if(c == '('){
stk.push(res);
op.push(sign);
res = 0;
sign = 1;
}
else if(c == ')'){
res = res * op.top();
op.pop();
res += stk.top();
stk.pop(>;
}
}
return res;
}
};
Input
s = "1 + 1"
Output
2
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int calculate(String s) {
Stack stack = new Stack<>();
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 = number * 10 + Character.getNumericValue(c);
} else if (c == '+' || c == '-') {
result += sign * number;
sign = c == '+' ? 1 : -1;
number = 0;
} else if (c == '(') {
stack.push(result);
stack.push(sign);
sign = 1;
result = 0;
} else if (c == ')') {
result += sign * number;
result *= stack.pop();
result += stack.pop();
number = 0;
}
}
return result + (sign * number);
}
}
Input
s = " 2-1 + 2 "
Output
3
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const calculate = function(s) {
let stack = []
let num = 0
let sign = 1
let res = 0
for (let i = 0; i < s.length; i++) {
let char = s.charAt(i)
if (char >= '0' && char <= '9') {
num = num * 10 + parseInt(char, 10)
} else if (char === '+') {
res += sign * num
sign = 1
num = 0
} else if (char === '-') {
res += sign * num
sign = -1
num = 0
} else if (char === '(') {
stack.push(res)
stack.push(sign)
sign = 1
res = 0
num = 0
} else if (char === ')') {
res += sign * num
res *= stack.pop()
res += stack.pop()
num = 0
}
}
return res + sign * num
}
Input
s = " 2-1 + 2 "
Output
3
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def calculate(self, s):
def calc(n2, op, n1):
return n1 + n2 if op == "+" else n1 - n2
stack, i, num = [], 0, 0
while i < len(s):
j = i
while j < len(s) and s[j].isdigit():
num, j = num * 10 + int(s[j]), j + 1
if i != j:
stack.append(calc(num, stack.pop(), stack.pop()) if stack and s[i - 1] != "(" else num)
num, j = 0, j - 1
elif s[i] in "+-":
stack.append(s[i])
elif s[i] == ")" and len(stack) > 1:
stack.append(calc(stack.pop(), stack.pop(), stack.pop()))
i = j + 1
return stack.pop()
Input
s = "(1+(4+5+2)-3)+(6+8)"
Output
23
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0224_BasicCalculator
{
public int Calculate(string s)
{
var stack = new Stack < int>();
int num = 0;
var sign = 1;
var result = 0;
foreach (var ch in s)
{
if (char.IsDigit(ch))
num = 10 * num + (ch - '0');
else if (ch == '+')
{
result += sign * num;
sign = 1;
num = 0;
}
else if (ch == '-')
{
result += sign * num;
sign = -1;
num = 0;
}
else if (ch == '(')
{
stack.Push(result);
stack.Push(sign);
sign = 1;
num = 0;
result = 0;
}
else if (ch == ')')
{
result += sign * num;
num = result;
sign = stack.Pop();
result = stack.Pop();
}
}
return result + sign * num;
}
}
}
Input
s = "(1+(4+5+2)-3)+(6+8)"
Output
23