算法:解析中缀表达式

算法 大约 2154 字

说明

未考虑小数、负数、括号问题。

定义计算结构体

type Calculator struct {
    NumTop        int
    OperatorTop   int
    NumStack      []float32
    OperatorStack []int32
}

定义计算方法

func (calc *Calculator) Calc() {
    last := calc.PopNum()
    previous := calc.PopNum()
    popOperator := calc.PopOperator()
    // - 号 需变换符号
    // 7-2+6 先运算2和6,则更换+为-
    if calc.PeekOperator() == '-' {
        if popOperator == '+'{
            popOperator = '-'
        } else if popOperator == '-'{
            popOperator = '+'
        }
    }
    num := Calc(previous, last, popOperator)
    calc.PutNum(num)
}

计算优先级

func Priority(operator int32) int {
    if operator == '*' || operator == '/' {
        return 1000
    } else if operator == '+' || operator == '-' {
        return 100
    } else {
        return 0
    }
}

处理字符串

func NewCalc(expression string) *Calculator {
    calc := &Calculator{-1, -1, make([]float32, 32), make([]int32, 32)}

    // 处理多位数
    keepNum := ""
    for i, v := range expression {
        if v >= 48 && v <= 57 {
            // 0-9
            keepNum += string(v)
            if i == len(expression)-1 {
                num, _ := strconv.Atoi(keepNum)
                calc.PutNum(float32(num))
            } else {
                if expression[i+1] < 48 || expression[i+1] > 57{
                    // 下一位操作符
                    num, _ := strconv.Atoi(keepNum)
                    calc.PutNum(float32(num))
                    keepNum = ""
                }
            }
        } else {
            // 操作符 + - * /
            operator := calc.PeekOperator()
            if operator == -1 {
                calc.PutOperator(v)
            } else if Priority(operator) >= Priority(v) {
                // 运算等级小于或等于,直接pop出NumStack两个数进行计算
                calc.Calc()
                calc.PutOperator(v)
            } else {
                calc.PutOperator(v)
            }
        }
    }

    for calc.PeekOperator() != -1 {
        calc.Calc()
    }

    fmt.Println("最终结果#", calc.PopNum())

    return calc
}

测试代码

func main() {
    expression := "2+7*2-2*4+6"
    calc := NewCalc(expression)
    fmt.Printf("%+v", calc)
}
阅读 48 · 发布于 2021-01-27

————        END        ————

扫描下方二维码关注公众号和小程序↓↓↓

扫描二维码关注我
昵称:
随便看看 换一批