# Basic Calculator

This page explains Java solution to problem `Basic Calculator` using `Stack` data structure.

## Problem Statement

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.

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class BasicCalculator {
public int calculate(String s) {
if(s == null || s.length() == 0) return 0;

for(int i = 0; i < s.length(); i++) {
q.offer(s.charAt(i));
}
q.offer('+');
return calculate(q);
}

private int calculate(Queue<Character> q) {
int num = 0;
Stack<Integer> st = new Stack<>();
int prevSign = '+';

while(!q.isEmpty()) {
char ch = q.poll();

if(ch == ' ') continue;

else if(Character.isDigit(ch)) {
num = num * 10 + ch - '0';
}
else if(ch == '(') {
num = calculate(q);
}
else {
if(prevSign == '+') {
st.push(num);
}
else if(prevSign == '-') {
st.push(-1 * num);
}
else if(prevSign == '*') {
st.push(st.pop() * num);
}
else if(prevSign == '/') {
st.push(st.pop() / num);
}

num = 0;
prevSign = ch;
if(ch == ')') break;
}
}

int sum = 0;
while(!st.isEmpty()) sum += st.pop();
return sum;
}
}
``````

## Time Complexity

O(N) Where
N is total number of elements in an input string

## Space Complexity

O(N) Where
N is total number of elements in an input string