给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右括号。返回公式的计算结果，难点在于括号可能嵌套很多层。str=“48*((70-65)-43)+81"，返回-1816。str="3+14”，返回7。str=“3+(14)"，返回7。【说明】 1.可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。2.如果是负数，就需要用括号括起来，比如“4(-3)”但如果负数作为公式的开头或括号部分的开头，则可以没有括号，比如”-34"和"(-34)"都是合法的。 3.不用考虑计算过程中会发生溢出的情况。
栈。对于递归函数。遇到左括号，递归调用；遇到右括号或者终止位置，终止。递归函数需要返回计算后的结果和终止位置。
代码用golang编写。代码如下：
package main
import (
"container/list"
"fmt"
"strconv"
)
func main() {
ret := calculate("(1+2/2)*3")
fmt.Println(ret)
}
func calculate(str string) int {
return f(str, 0).Val
}
type RetInfo struct {
Val int
Index int
}
// 请从str[i...]往下算，遇到字符串终止位置或者右括号，就停止
// 返回两个值，长度为2的数组
// 0) 负责的这一段的结果是多少
// 1) 负责的这一段计算到了哪个位置
func f(str string, i int) *RetInfo {
que := list.New().Init()
cur := 0
var bra *RetInfo
// 从i出发，开始撸串
for i < len(str) && str[i] != ')' {
if str[i] >= '0' && str[i] <= '9' {
cur = cur*10 + int(str[i]-'0')
i++
} else if str[i] != '(' { // 遇到的是运算符号
addNum(que, cur)
que.PushBack(fmt.Sprintf("%c", str[i]))
i++
cur = 0
} else { // 遇到左括号了
bra = f(str, i+1)
cur = bra.Val
i = bra.Index + 1
}
}
addNum(que, cur)
return &RetInfo{Val: getNum(que), Index: i}
}
func addNum(que *list.List, num int) {
if que.Len() > 0 {
cur := 0
top := que.Back().Value.(string)
que.Remove(que.Back())
if top == "+" || top == "-" {
que.PushBack(top)
} else {
cur, _ = strconv.Atoi(que.Back().Value.(string))
que.Remove(que.Back())
if top == "*" {
num = cur * num
} else {
num = cur / num
}
}
}
que.PushBack(fmt.Sprintf("%d", num))
}
func getNum(que *list.List) int {
res := 0
add := true
var cur string
num := 0
for que.Len() > 0 {
cur = que.Front().Value.(string)
que.Remove(que.Front())
if cur == "+" {
add = true
} else if cur == "-" {
add = false
} else {
num, _ = strconv.Atoi(cur)
if add {
res += num
} else {
res -= num
}
}
}
return res
}执行结果如下：
