2021-05-23：给定一个字符串str，str表示一个公式，公式里可能有

2021-05-23：给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右括号。返回公式的计算结果，难点在于括号可能嵌套很多层。str=”48*((70-65)-43)+8*1″，返回-1816。str=”3+1*4″，返回7。str=”3+(1*4)”，返回7。【说明】 1.可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。2.如果是负数，就需要用括号括起来，比如“4*(-3)”但如果负数作为公式的开头或括号部分的开头，则可以没有括号，比如”-3*4″和”(-3*4)”都是合法的。 3.不用考虑计算过程中会发生溢出的情况。

福大大 答案2021-05-23：

栈。对于递归函数。遇到左括号，递归调用；遇到右括号或者终止位置，终止。递归函数需要返回计算后的结果和终止位置。

代码用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
}  

执行结果如下：

***

[左神java代码](