算法:中缀表达式转后缀表达式

算法 大约 3038 字

调度场算法

中缀表达式转后缀表达式又称调度场算法。

可参考 维基百科:调度场算法

算法步骤

  1. 从左到右扫描中缀表达式
  2. 遇到操作数直接入栈s2
  3. 遇到运算符时,比较运算符栈s1的栈顶运算符的优先级 2.1 若s1为空,或栈顶运算符为左括号(则直接入s1 2.2 若遇到的运算符比s1栈顶的运算符优先级高,则直接入s1 2.3 若遇到的运算符比s1栈顶的运算符优先级小或等于,则先弹出s1栈顶的运算符压入到s2中,再跳转至2.1s1新的栈顶运算符进行比较
  4. 遇到括号时 3.1 若遇到的是左括号(则直接入s2栈 3.2 若遇到的是右括号)则依次弹出s1中的运算符并压入s2,直到遇到右括号为止,并将一对括号丢弃
  5. s1剩余栈压入s2
  6. s2pop出的元素的逆序即中缀表达式转后缀表达式的结果

辅助方法

IsOperator:判断是否是运算符。

CalcValue:两数运算。

CalcPriority:操作数计算运算优先级。

func IsOperator(char string) bool {
    return char == "+" || char == "-" || char == "*" || char == "/" || char == "(" || char == ")"
}

func CalcValue(num1, num2 float32, operator string) float32 {
    if operator == "*" {
        return num1 * num2
    } else if operator == "/" {
        return num1 / num2
    } else if operator == "+" {
        return num1 + num2
    } else if operator == "-" {
        return num1 - num2
    } else {
        return -1
    }
}

func CalcPriority(operator string) int {
    if operator == "*" || operator == "/" {
        return 1000
    } else if operator == "+" || operator == "-" {
        return 100
    } else {
        return 0
    }
}

实现

后缀表达式的计算方式:从左往右扫描后缀表达式,遇到数字放入数字栈,遇到运算符则弹出数字栈中的两个元素,栈顶的元素作为后一个元素,次顶元素作为前一个元素,如:A-B减法运算中A是次顶元素,B是栈顶元素,将运算完成得到的数再次入数字栈,步骤循环,最后在数字栈中只剩最后一个元素即是后缀表达式的最终结果。

func main() {
    infixNotationExpression := "1+((2+3)*4)-5"
    arr1 := strings.Split(infixNotationExpression, "")
    finalStr := ""
    stack := &Stack{-1, make([]interface{}, 10)}
    for _, str := range arr1 {
        if IsOperator(str) {
            if str == "(" {
                // 入运算符栈
                stack.Put(str)
            } else if str == ")" {
                // pop 到 ( 为止
                for stack.Peek().(string) != "(" {
                    finalStr += stack.Pop().(string) + " "
                }
                stack.Pop()
            } else {
                for {
                    empty := stack.IsEmpty()
                    if !empty && (CalcPriority(str) <= CalcPriority(stack.Peek().(string))) {
                        finalStr += stack.Pop().(string) + " "
                    } else {
                        // 入运算符栈
                        stack.Put(str)
                        break
                    }
                }
            }
        } else {
            finalStr += str + " "
        }
    }

    // 将运算符中的元素都弹出压入s2
    for !stack.IsEmpty() {
        finalStr += stack.Pop().(string) + " "
    }

    finalStr = strings.TrimRight(finalStr," ")
    fmt.Println("finalStr#", finalStr)

    //expression := "3 4 + 5 * 6 -"
    arr := strings.Split(finalStr, " ")
    numStack := &Stack{-1, make([]interface{}, 10)}
    for _, value := range arr {
        if IsOperator(value) {
            after := numStack.Pop()  // 栈顶
            before := numStack.Pop() // 次顶
            num := CalcValue(before.(float32), after.(float32), value)
            numStack.Put(num)
        } else {
            num, _ := strconv.ParseFloat(value, 32)
            numStack.Put(float32(num))
        }
    }

    fmt.Println(numStack.Pop())
}
阅读 64 · 发布于 2021-01-28

————        END        ————

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

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