NUHMAN.com

🧩 Problem Statement

Given a string representing a mathematical expression, implement a basic calculator to evaluate it. The expression may contain the following operators: +, -, *, /. The integer division should truncate toward zero. You may assume that the given expression is always valid. Operators +, -, *, / have the same precedence (left to right) and there are no parentheses.

You need to implement the following function:

go

func calculate(s string) int

📘 Example

go

Input: s = "3+2*2"
Output: 7

Input: s = "3/2"
Output: 1

Input: s = "3+5/2"
Output: 5

📝 Explanation:

1. Example 1:

• "3+2*2" → We first do multiplication (2*2 = 4), then addition (3+4 = 7).

1. Example 2:

• "3/2" → Integer division (3/2 = 1).

1. Example 3:

• "3+5/2" → Integer division (5/2 = 2), then addition (3+2 = 5).

🧠 Approach

We need to evaluate the mathematical expression from left to right, respecting operator precedence. The approach is as follows:

Steps:

1. Traverse through the expression character by character:

• If the character is a number, keep reading the digits to form the full number.
• If the character is an operator (+, -, *, /), perform the calculation according to the precedence of the operators.

1. Operator Precedence:

• * and / have higher precedence than + and -. Perform multiplication or division immediately when encountered.
• For + and -, store the result of the previous operation and perform addition or subtraction at the end.

1. Using a Stack:

• Use a stack to store intermediate results. When encountering a * or / operator, calculate immediately and replace the value on the stack.
• For + and -, store the result of the current value in the stack and continue.

✅ Go Implementation

go

package main

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

// Function to calculate the result of the given expression
func calculate(s string) int {
	stack := []int{}
	num := 0
	sign := 1 // 1 for '+', -1 for '-'
	
	for i := 0; i < len(s); i++ {
		c := s[i]
		
		// If the character is a digit, form the number
		if unicode.IsDigit(rune(c)) {
			num = num*10 + int(c-'0')
		}
		
		// If the character is an operator or we reach the end
		if (!unicode.IsDigit(rune(c)) && c != ' ') || i == len(s)-1 {
			switch sign {
			case 1: // previous sign was '+'
				stack = append(stack, num)
			case -1: // previous sign was '-'
				stack = append(stack, -num)
			}
			
			// If the operator is '*' or '/', calculate immediately
			if c == '*' {
				num = 0
				sign = 0 // reset sign for '*' or '/'
				for i+1 < len(s) && unicode.IsDigit(rune(s[i+1])) {
					i++
					num = num*10 + int(s[i]-'0')
				}
				stack[len(stack)-1] = stack[len(stack)-1] * num
			} else if c == '/' {
				num = 0
				sign = 0 // reset sign for '*' or '/'
				for i+1 < len(s) && unicode.IsDigit(rune(s[i+1])) {
					i++
					num = num*10 + int(s[i]-'0')
				}
				stack[len(stack)-1] = stack[len(stack)-1] / num
			}
			
			// Reset num for next number
			num = 0
			// Update sign based on the operator
			if c == '+' {
				sign = 1
			} else if c == '-' {
				sign = -1
			}
		}
	}
	
	// Sum up all the values in the stack to get the final result
	result := 0
	for _, val := range stack {
		result += val
	}
	return result
}

// Helper function to test the calculate function
func main() {
	// Test cases
	fmt.Println(calculate("3+2*2"))   // Output: 7
	fmt.Println(calculate("3/2"))      // Output: 1
	fmt.Println(calculate("3+5/2"))    // Output: 5
	fmt.Println(calculate("3-2-1"))    // Output: 0
	fmt.Println(calculate("3+2*2/2"))  // Output: 5
}

📦 Example Usage

go

func main() {
	// Test cases
	fmt.Println(calculate("3+2*2"))   // Output: 7
	fmt.Println(calculate("3/2"))      // Output: 1
	fmt.Println(calculate("3+5/2"))    // Output: 5
	fmt.Println(calculate("3-2-1"))    // Output: 0
	fmt.Println(calculate("3+2*2/2"))  // Output: 5
}

⏱️ Time & Space Complexity

• Time Complexity:
• O(n), where n is the length of the string s. We iterate through the string once.
• Space Complexity:
• O(n), where n is the number of digits in the expression. In the worst case, the stack will store all the values in the expression.

This solution efficiently handles the problem of evaluating a mathematical expression with the basic operators, following the operator precedence.