首页 > 电脑常识 > 区块链

2021-05-23:给定一个字符串str,str表示一个公式,公式里可能有整数、加减乘除符号和左右括号。返回公式的计算结果,难点在于括号可能嵌套很多层。str=“48*((70-65)-43)+8*

admin 区块链 2021-05-25 09:26:32 算法 
后台-系统设置-扩展变量-手机广告位-内容正文底部

2021-05-23:给定一个字符串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.不用考虑计算过程中会发生溢出的情况。

福大大 答案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代码

文章来源:https://blog.csdn.net/weixin_48502062/article/details/117202044

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://www.jcdi.cn/qukuailian/30807.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码