## 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 * 105`
• `s` consists of digits, `'+'`, `'-'`, `'('`, `')'`, and `' '`.
• `s` represents 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;
}
``````
Copy The Code &

Input

cmd
s = "1 + 1"

Output

cmd
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;
}
};
``````
Copy The Code &

Input

cmd
s = "1 + 1"

Output

cmd
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);
}
}
``````
Copy The Code &

Input

cmd
s = " 2-1 + 2 "

Output

cmd
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
}
``````
Copy The Code &

Input

cmd
s = " 2-1 + 2 "

Output

cmd
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()
``````
Copy The Code &

Input

cmd
s = "(1+(4+5+2)-3)+(6+8)"

Output

cmd
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;
}
}
}
``````
Copy The Code &

Input

cmd
s = "(1+(4+5+2)-3)+(6+8)"

Output

cmd
23