題目

實現一個基本的計算器來計算一個簡單的字串表示式 s 的值。

示例 1：輸入：s = "1 + 1" 輸出：2

示例 2：輸入：s = " 2-1 + 2 " 輸出：3

示例 3：輸入：s = "(1+(4+5+2)-3)+(6+8)" 輸出：23

提示：1 <= s.length <= 3 * 105

s 由數字、'+'、'-'、'('、')'、和 ' ' 組成

s 表示一個有效的表示式

1、棧；時間複雜度O(n)，空間複雜度O(n)

func calculate(s string) int {	stack := make([]int, 0)	num := 0	res := 0	sign := 1	for i := 0; i < len(s); i++ {		if '0' <= s[i] && s[i] <= '9' {			num = 0			for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {				num = num*10 + int(s[i]-'0')			}			res = res + sign*num			i--		} else if s[i] == '+' {			sign = 1		} else if s[i] == '-' {			sign = -1		} else if s[i] == '(' {			stack = append(stack, res, sign)			res = 0			sign = 1		} else if s[i] == ')' {			sign = stack[len(stack)-1]			prev := stack[len(stack)-2]			stack = stack[:len(stack)-2]			res = prev + sign*res*sign		}	}	return res}

Hard題目，計算器系列題目，類似的題目還有 leetcode 227.基本計算器II