NUHMAN.com

🧩 Problem Statement

Implement a basic calculator to evaluate a simple mathematical expression string that contains non-negative integers, +, - operators, and parentheses.

You may assume that the given expression is valid and does not contain any invalid characters. There are no division or multiplication operators.

📘 Example

go

Input: "1 + 1"
Output: 2

Input: "2 - 1 + 2"
Output: 3

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

📝 Explanation:

• In the first example, the expression "1 + 1" evaluates to 2.
• In the second example, the expression "2 - 1 + 2" evaluates to 3.
• In the third example, the expression involves nested parentheses, so we must evaluate from inside the parentheses first, resulting in 23.

🧠 Approach

To evaluate the given mathematical expression, we'll simulate the operations by iterating over the string and maintaining the necessary state. Specifically:

1. Use a stack to keep track of numbers and handle parentheses properly.
2. Iterate through the string, handling digits, operators, and parentheses:

• When encountering a digit, accumulate it and push it to the stack.
• When encountering an operator (+ or -), apply it to the current number.
• When encountering a left parenthesis ((), push a marker to signify entering a new scope.
• When encountering a right parenthesis ()), pop the stack until the left parenthesis is found and compute the result for that scope.

1. At the end of the iteration, sum up the values from the stack for the final result.

Steps:

1. Traverse the expression character by character.
2. Use a stack to handle parentheses and maintain intermediate results.
3. Handle the signs (+ and -) and compute the running total.

✅ Go Implementation

go

package main

import (
	"fmt"
	"strconv"
	"unicode"
)

// Function to evaluate the expression
func calculate(s string) int {
	stack := []int{}
	currentNum := 0
	sign := 1  // 1 for positive, -1 for negative
	result := 0

	for i := 0; i < len(s); i++ {
		ch := s[i]

		// If the character is a digit, build the current number
		if unicode.IsDigit(rune(ch)) {
			currentNum = currentNum*10 + int(ch-'0')
		} else if ch == '+' {
			// Apply the previous sign to the current number and add it to result
			result += sign * currentNum
			currentNum = 0
			sign = 1
		} else if ch == '-' {
			// Apply the previous sign to the current number and add it to result
			result += sign * currentNum
			currentNum = 0
			sign = -1
		} else if ch == '(' {
			// Push the result and sign onto the stack for later
			stack = append(stack, result)
			stack = append(stack, sign)
			result = 0
			sign = 1
		} else if ch == ')' {
			// Pop the sign and the previous result from the stack
			result += sign * currentNum
			currentNum = 0
			result *= stack[len(stack)-1]  // Apply the sign before the parentheses
			stack = stack[:len(stack)-1]
			result += stack[len(stack)-1]  // Add the result before the parentheses
			stack = stack[:len(stack)-1]
		}
	}

	// Add the last number
	result += sign * currentNum
	return result
}

func main() {
	// Test cases
	fmt.Println(calculate("1 + 1"))                // Output: 2
	fmt.Println(calculate("2 - 1 + 2"))            // Output: 3
	fmt.Println(calculate("(1+(4+5+2)-3)+(6+8)"))  // Output: 23
}

📦 Example Usage

go

func main() {
	// Test case examples
	fmt.Println(calculate("1 + 1"))                // Output: 2
	fmt.Println(calculate("2 - 1 + 2"))            // Output: 3
	fmt.Println(calculate("(1+(4+5+2)-3)+(6+8)"))  // Output: 23
}

⏱️ Time & Space Complexity

• Time Complexity: O(n), where n is the length of the expression string. We process each character exactly once.
• Space Complexity: O(n), due to the use of the stack which could store up to n elements in the worst case (e.g., nested parentheses).

This approach efficiently handles the evaluation of the expression, taking care of operator precedence and parentheses.