Solution For Basic Calculator

Problem Statement:

Design a basic calculator that can evaluate a simple arithmetic expression.

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: ” 2-1 + 2 ”
Output: 3

Example 3:

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

Note:
1. You may assume that the given expression is always valid.
2. Do not use the eval built-in library function.

Solution:

The approach to solve this problem is to use a stack. We will iterate the expression string character by character and evaluate the expression. In the stack, we will keep track of the numbers and operators in the expression.

We also need to handle the open and closing parentheses. Whenever we encounter an open parenthesis, we push the current result and operator into the stack and reset the result and operator. When we encounter a closing parenthesis, we pop the last result and operator from the stack and evaluate them with the current result using the popped operator.

Algorithm Steps:

1. Create an empty stack for numbers and an operator to track the current operator.
2. Iterate through the expression string from left to right:
   a. If the current character is a digit, start storing all consecutive digits (which could be a multi-digit number).
   b. If the current character is a plus or minus sign, set the current operator to this sign.
   c. If the current character is an open parenthesis, push the current result and operator to the stack, reset the result to 0, and set the operator to an open parenthesis.
   d. If the current character is a closing parenthesis, pop the last result and operator from the stack, evaluate them with the current result using the popped operator, and set the new result as the current result.
   f. Continue to the next character until the end of the string is reached.
3. After iterating through the string, return the final result.

Python Code:

def calculate(s):
stack = [] num = 0
op = “+”
result = 0
for i in range(len(s)):
if s[i].isdigit():
num = num * 10 + int(s[i])
if s[i] in “+-/” or i == len(s) – 1:
if op == “+”:
stack.append(num)
elif op == “-“:
stack.append(-num)
elif op == ““:
stack.append(stack.pop() * num)
elif op == “/”:
stack.append(int(stack.pop() / num))
num = 0
op = s[i] while stack:
result += stack.pop()
return result

Test Cases

print(calculate(“1 + 1″)) # Output: 2
print(calculate(” 2-1 + 2 “)) # Output: 3
print(calculate(“(1+(4+5+2)-3)+(6+8)”)) # Output: 23

Time Complexity: The time complexity of the above solution is O(n) where n is the length of the expression string.

Space Complexity: The space complexity of the above solution is O(n) where n is the length of the expression string. This is because we are using a stack to store the numbers and operators in the expression.

Step by Step Implementation For Basic Calculator

/**
 * 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: " 2-1 + 2 "
 * Output: 3
 * Example 3:
 * 
 * Input: "(1+(4+5+2)-3)+(6+8)"
 * Output: 23
 * Note:
 * You may assume that the given expression is always valid.
 * Do not use the eval built-in library function.
 */

class Solution {
    public int calculate(String s) {
        // Base case
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        // Initialize stack
        Stack stack = new Stack<>();
        int result = 0;
        int sign = 1;
        
        // Loop through string
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            // If digit, convert to number
            if (Character.isDigit(c)) {
                int num = c - '0';
                // Build number
                while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                    num = num * 10 + (s.charAt(i + 1) - '0');
                    i++;
                }
                // Add number to result
                result += sign * num;
            } 
            // If '+', update sign to positive
            else if (c == '+') {
                sign = 1;
            } 
            // If '-', update sign to negative
            else if (c == '-') {
                sign = -1;
            } 
            // If '(', push result and sign to stack
            else if (c == '(') {
                stack.push(result);
                stack.push(sign);
                // Reset result and sign for next calculation
                result = 0;
                sign = 1;
            } 
            // If ')', pop from stack
            else if (c == ')') {
                // Pop sign and result from stack
                result = result * stack.pop() + stack.pop();
            }
        }
        return result;
    }
}

class Solution:
    def calculate(self, s: str) -> int:
        # This is a basic calculator that can handle +, -, *, /, and ()
        # It uses a stack to keep track of operations and operands
        
        # Create a stack
        stack = []
        
        # Create a variable to keep track of the sign
        sign = 1
        
        # Create a variable to store the result
        result = 0
        
        # Loop through the string
        for i in range(len(s)):
            
            # Get the current character
            curr = s[i]
            
            # If the character is a digit, convert it to an int and add it to the result
            if curr.isdigit():
                result = result * 10 + int(curr)
            
            # If the character is a '+', push the result to the stack and reset the result
            elif curr == '+':
                stack.append(result)
                stack.append(sign)
                result = 0
                sign = 1
            
            # If the character is a '-', push the result to the stack and reset the result
            elif curr == '-':
                stack.append(result)
                stack.append(sign)
                result = 0
                sign = -1
            
            # If the character is a '*', get the next number and multiply it by the result
            elif curr == '*':
                result = result * int(s[i+1])
                i += 1
            
            # If the character is a '/', get the next number and divide the result by it
            elif curr == '/':
                result = int(result / int(s[i+1]))
                i += 1
            
            # If the character is a '(', push the result and the sign to the stack and reset the result and sign
            elif curr == '(':
                stack.append(result)
                stack.append(sign)
                result = 0
                sign = 1
            
            # If the character is a ')', pop the stack twice (once for the sign and once for the number)
            # and multiply the number by the sign and add it to the result
            elif curr == ')':
                result = result * stack.pop()
                result = result + stack.pop()
        
        # Return the result
        return result

var calculate = function(s) {
    let stack = [], num = 0, sign = 1;
    for(let i = 0; i < s.length; i++){
        if(s.charAt(i) == ' ') continue;
        else if(s.charAt(i) == '+'){
            sign = 1;
        }
        else if(s.charAt(i) == '-'){
            sign = -1;
        }
        else if(s.charAt(i) == '('){
            stack.push(num);
            stack.push(sign);
            num = 0;
            sign = 1;
        }
        else if(s.charAt(i) == ')'){
            num = num*sign + stack.pop();
            sign = stack.pop();
        }
        else{
            num = num*10 + (s.charAt(i) - '0');
        }
    }
    return num*sign;
};

class Solution {
public:
    int calculate(string s) {
        int n = s.size();
        int res = 0;
        int sign = 1;
        stack st;
        for (int i = 0; i < n; ++i) {
            if (s[i] == ' ') continue;
            if (s[i] == '+') {
                sign = 1;
            } else if (s[i] == '-') {
                sign = -1;
            } else if (s[i] == '(') {
                st.push(res);
                st.push(sign);
                res = 0;
                sign = 1;
            } else if (s[i] == ')') {
                res = res * st.top() + st.top(-1);
                st.pop();
                st.pop();
            } else {
                int num = s[i] - '0';
                while (i + 1 < n && isdigit(s[i + 1])) {
                    num = num * 10 + s[i + 1] - '0';
                    ++i;
                }
                res += num * sign;
            }
        }
        return res;
    }
};

using System; 

public class Solution {
    public int Calculate(string s) {
        if (s == null || s.Length == 0) return 0;
        int sign = 1, res = 0, i = 0;
        Stack stack = new Stack();
        while (i < s.Length) {
            if (Char.IsDigit(s[i])) {
                int num = s[i] - '0';
                while (i + 1 < s.Length && Char.IsDigit(s[i + 1])) {
                    num = num * 10 + s[i + 1] - '0';
                    i++;
                }
                res += sign * num;
            }
            else if (s[i] == '+') sign = 1;
            else if (s[i] == '-') sign = -1;
            else if (s[i] == '(') {
                stack.Push(res);
                stack.Push(sign);
                res = 0;
                sign = 1;
            }
            else if (s[i] == ')') {
                res = res * stack.Pop() + stack.Pop();
            }
            i++;
        }
        return res;
    }
}