0224. Basic Calculator

# 224. 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.

## 解题思路 #

• 注意点一：算式中有空格，需要跳过
• 注意点二：算式中会出现负数，负负得正的情况需要特殊处理，所以需要记录每次计算出来的符号

## 代码 #

``````
package leetcode

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

// 解法一
func calculate(s string) int {
i, stack, result, sign := 0, list.New(), 0, 1 // 记录加减状态
for i < len(s) {
if s[i] == ' ' {
i++
} else if s[i] <= '9' && s[i] >= '0' { // 获取一段数字
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] == '(' { // 把之前计算结果及加减状态压栈，开始新的计算
stack.PushBack(result)
stack.PushBack(sign)
result = 0
sign = 1
i++
} else if s[i] == ')' { // 新的计算结果 * 前一个加减状态 + 之前计算结果
result = result*stack.Remove(stack.Back()).(int) + stack.Remove(stack.Back()).(int)
i++
}
}
return result
}

// 解法二
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
// 处理符号的问题，++得+，--得+，+-、-+得-
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
}

``````

Sep 6, 2020