224. Basic Calculator #

Problem #

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.

Problem Summary #

Implement a basic calculator to calculate the value of a simple string expression. The string expression may contain left parentheses (, right parentheses ), plus signs +, minus signs -, non-negative integers, and spaces.

Solution Ideas #

Note 1: There are spaces in the expression, which need to be skipped
Note 2: Negative numbers may appear in the expression, and cases where two negatives make a positive need special handling, so the sign calculated each time needs to be recorded

Code #


package leetcode

import (
	"container/list"
	"fmt"
	"strconv"
)

// Solution 1
func calculate(s string) int {
	i, stack, result, sign := 0, list.New(), 0, 1 // Record addition/subtraction state
	for i < len(s) {
		if s[i] == ' ' {
			i++
		} else if s[i] <= '9' && s[i] >= '0' { // Get a sequence of digits
			base, v := 10, int(s[i]-'0')
			for i+1 < len(s) && s[i+1] <= '9' && s[i+1] >= '0' {
				v = v*base + int(s[i+1]-'0')
				i++
			}
			result += v * sign
			i++
		} else if s[i] == '+' {
			sign = 1
			i++
		} else if s[i] == '-' {
			sign = -1
			i++
		} else if s[i] == '(' { // Push the previous calculation result and addition/subtraction state onto the stack, and start a new calculation
			stack.PushBack(result)
			stack.PushBack(sign)
			result = 0
			sign = 1
			i++
		} else if s[i] == ')' { // New calculation result * previous addition/subtraction state + previous calculation result
			result = result*stack.Remove(stack.Back()).(int) + stack.Remove(stack.Back()).(int)
			i++
		}
	}
	return result
}

// Solution 2
func calculate1(s string) int {
	stack := []byte{}
	for i := 0; i < len(s); i++ {
		if s[i] == ' ' {
			continue
		} else if s[i] == ')' {
			tmp, index := "", len(stack)-1
			for ; index >= 0; index-- {
				if stack[index] == '(' {
					break
				}
			}
			tmp = string(stack[index+1:])
			stack = stack[:index]
			res := strconv.Itoa(calculateStr(tmp))
			for j := 0; j < len(res); j++ {
				stack = append(stack, res[j])
			}
		} else {
			stack = append(stack, s[i])
		}
	}
	fmt.Printf("stack = %v\n", string(stack))
	return calculateStr(string(stack))
}

func calculateStr(str string) int {
	s, nums, tmpStr, res := []byte{}, []int{}, "", 0
	// Handle signs: ++ gives +, -- gives +, +- and -+ give -
	for i := 0; i < len(str); i++ {
		if len(s) > 0 && s[len(s)-1] == '+' && str[i] == '+' {
			continue
		} else if len(s) > 0 && s[len(s)-1] == '+' && str[i] == '-' {
			s[len(s)-1] = '-'
		} else if len(s) > 0 && s[len(s)-1] == '-' && str[i] == '+' {
			continue
		} else if len(s) > 0 && s[len(s)-1] == '-' && str[i] == '-' {
			s[len(s)-1] = '+'
		} else {
			s = append(s, str[i])
		}
	}
	str = string(s)
	s = []byte{}
	for i := 0; i < len(str); i++ {
		if isDigital(str[i]) {
			tmpStr += string(str[i])
		} else {
			num, _ := strconv.Atoi(tmpStr)
			nums = append(nums, num)
			tmpStr = ""
			s = append(s, str[i])
		}
	}
	if tmpStr != "" {
		num, _ := strconv.Atoi(tmpStr)
		nums = append(nums, num)
	}
	res = nums[0]
	for i := 0; i < len(s); i++ {
		if s[i] == '+' {
			res += nums[i+1]
		} else {
			res -= nums[i+1]
		}
	}
	fmt.Printf("s = %v nums = %v res = %v\n", string(s), nums, res)
	return res
}

func isDigital(v byte) bool {
	if v >= '0' && v <= '9' {
		return true
	}
	return false
}