主页 / 问题 / 1597478
Accepted
Mason
Asked:2024-10-22 19:13:48 +0000 UTC2024-10-22 19:13:48 +0000 UTC

go 的线性计算器

  • 772

一个行计算器，在测试系统检查时，给出错误：超出了程序执行时间限制（某些情况下程序进入死循环，我认为有些错误情况没有被考虑到。

使用两个堆栈实现，其中一个是操作，另一个是数字。

我从视频中获取了操作原理：https://youtu.be/Vk-tGND2bfc?si= c4RzRBDehfykDRlm

这是问题陈述：

实现一个函数func Calc(expression string) (float64, error)，其中表达式是由单字符标识符和算术运算符号组成的字符串表达式 输入数据 - 数字（有理数）、运算 +、-、*、/、优先运算（和 ） 写入错误的情况表达式，该函数会生成错误。

这是代码：

package main

import (
    "errors"
    "fmt"
    "strconv"
    "unicode"
)

func Calc(expression string) (float64, error) {
    priority := map[rune]int{'+': 1, '-': 1, '*': 2, '/': 2}
    var num []float64
    var operator []rune
    var hasNumber bool

    for _, ch := range expression {
        if unicode.IsDigit(ch) {
            hasNumber = true
        }
    }

    if !hasNumber {
        return 0, errors.New("no number")
    }

    if len(expression) == 0 {
        return 0, errors.New("empty expression")
    }

    check := rune(expression[len(expression)-1])
    if !unicode.IsDigit(check) && check != ')' {
        return 0, errors.New("invalid, last char is not digits or closing bracket")
    }

    applyOperator := func(a, b float64, op rune) float64 {
        switch op {
        case '+':
            return a + b
        case '-':
            return a - b
        case '*':
            return a * b
        case '/':
            if b == 0 {
                panic("division by zero")
            }
            return a / b
        default:
            return 0
        }
    }

    calculate := func() {
        if len(operator) == 0 || len(num) < 2 {
            return
        }
        b := num[len(num)-1]
        a := num[len(num)-2]
        op := operator[len(operator)-1]
        num = num[:len(num)-2]
        operator = operator[:len(operator)-1]
        result := applyOperator(a, b, op)
        num = append(num, result)
    }

    for i := 0; i < len(expression); i++ {
        ch := rune(expression[i])

        if unicode.IsDigit(ch) || ch == '.' {
            start := i
            for i < len(expression) && (unicode.IsDigit(rune(expression[i])) || expression[i] == '.') {
                i++
            }
            numer, err := strconv.ParseFloat(expression[start:i], 64)
            if err != nil {
                return 0, fmt.Errorf("failed to parse number: %v", err)
            }
            num = append(num, numer)
            i--
        } else if ch == '+' || ch == '-' {
            if i == 0 || expression[i-1] == '(' || len(operator) > 0 && operator[len(operator)-1] == '(' {
                num = append(num, 0)
            }
            for len(operator) > 0 && priority[operator[len(operator)-1]] >= priority[ch] {
                calculate()
            }
            operator = append(operator, ch)
        } else if ch == '*' || ch == '/' {
            for len(operator) > 0 && priority[operator[len(operator)-1]] >= priority[ch] {
                calculate()
            }
            operator = append(operator, ch)
        } else if ch == '(' {
            operator = append(operator, ch)
        } else if ch == ')' {
            for len(operator) > 0 && operator[len(operator)-1] != '(' {
                calculate()
            }
            if len(operator) == 0 {
                return 0, errors.New("mismatched parentheses")
            }
            operator = operator[:len(operator)-1]
        } else if !unicode.IsSpace(ch) {
            return 0, errors.New("invalid character")
        }
    }

    for len(operator) > 0 {
        calculate()
    }

    if len(num) == 1 {
        return num[0], nil
    }

    return 0, errors.New("invalid expression")
}
golang

1 个回答

  1. Best Answer
    package main

import (
    "errors"
    "fmt"
    "strconv"
    "strings"
)

// Calc evaluates a mathematical expression given as a string.
func Calc(expression string) (float64, error) {
    tokens := tokenize(expression)
    postfix, err := infixToPostfix(tokens)
    if err != nil {
        return 0, err
    }
    return evaluatePostfix(postfix)
}

// tokenize splits the expression into tokens.
func tokenize(expr string) []string {
    var tokens []string
    var currentToken strings.Builder

    for _, char := range expr {
        switch char {
        case ' ':
            continue
        case '+', '-', '*', '/', '(', ')':
            if currentToken.Len() > 0 {
                tokens = append(tokens, currentToken.String())
                currentToken.Reset()
            }
            tokens = append(tokens, string(char))
        default:
            currentToken.WriteRune(char)
        }
    }

    if currentToken.Len() > 0 {
        tokens = append(tokens, currentToken.String())
    }

    return tokens
}

// infixToPostfix converts an infix expression to postfix notation using the Shunting Yard algorithm.
func infixToPostfix(tokens []string) ([]string, error) {
    var output []string
    var operators []string

    for _, token := range tokens {
        if isNumber(token) {
            output = append(output, token)
        } else if token == "(" {
            operators = append(operators, token)
        } else if token == ")" {
            for len(operators) > 0 && operators[len(operators)-1] != "(" {
                output = append(output, operators[len(operators)-1])
                operators = operators[:len(operators)-1]
            }
            if len(operators) == 0 {
                return nil, errors.New("mismatched parentheses")
            }
            operators = operators[:len(operators)-1] // Pop the '('
        } else if isOperator(token) {
            for len(operators) > 0 && precedence(operators[len(operators)-1]) >= precedence(token) {
                output = append(output, operators[len(operators)-1])
                operators = operators[:len(operators)-1]
            }
            operators = append(operators, token)
        } else {
            return nil, fmt.Errorf("invalid character")
        }
    }

    for len(operators) > 0 {
        if operators[len(operators)-1] == "(" {
            return nil, errors.New("mismatched parentheses")
        }
        output = append(output, operators[len(operators)-1])
        operators = operators[:len(operators)-1]
    }

    return output, nil
}

// evaluatePostfix evaluates a postfix expression.
func evaluatePostfix(postfix []string) (float64, error) {
    var stack []float64

    for _, token := range postfix {
        if isNumber(token) {
            num, _ := strconv.ParseFloat(token, 64)
            stack = append(stack, num)
        } else if isOperator(token) {
            if len(stack) < 2 {
                return 0, errors.New("invalid expression")
            }
            b := stack[len(stack)-1]
            a := stack[len(stack)-2]
            stack = stack[:len(stack)-2]

            switch token {
            case "+":
                stack = append(stack, a+b)
            case "-":
                stack = append(stack, a-b)
            case "*":
                stack = append(stack, a*b)
            case "/":
                if b == 0 {
                    return 0, errors.New("division by zero")
                }
                stack = append(stack, a/b)
            default:
                return 0, fmt.Errorf("unknown operator: %s", token)
            }
        } else {
            return 0, fmt.Errorf("invalid token: %s", token)
        }
    }

    if len(stack) != 1 {
        return 0, errors.New("invalid expression")
    }

    return stack[0], nil
}

// isNumber checks if a token is a number.
func isNumber(token string) bool {
    if _, err := strconv.ParseFloat(token, 64); err == nil {
        return true
    }
    return false
}

// isOperator checks if a token is an operator.
func isOperator(token string) bool {
    return token == "+" || token == "-" || token == "*" || token == "/"
}

// precedence returns the precedence of an operator.
func precedence(op string) int {
    switch op {
    case "+", "-":
        return 1
    case "*", "/":
        return 2
    default:
        return 0
    }
}

func main() {
    expression := "3 + 5 * (2 - 8)"
    result, err := Calc(expression)
    if err != nil {
        fmt.Println("Error:", err)
    } else {
        fmt.Println("Result:", result)
    }
}
    • 0

相关问题