算法:中缀表达式转后缀表达式
算法 About 3,038 words调度场算法
中缀表达式转后缀表达式又称调度场算法。
可参考 维基百科:调度场算法
算法步骤
- 从左到右扫描中缀表达式
- 遇到操作数直接入栈
s2
- 遇到运算符时,比较运算符栈
s1
的栈顶运算符的优先级 2.1 若s1
为空,或栈顶运算符为左括号(
则直接入s1
2.2 若遇到的运算符比s1
栈顶的运算符优先级高,则直接入s1
2.3 若遇到的运算符比s1
栈顶的运算符优先级小或等于,则先弹出s1
栈顶的运算符压入到s2
中,再跳转至2.1
与s1
新的栈顶运算符进行比较 - 遇到括号时
3.1 若遇到的是左括号
(
则直接入s2
栈 3.2 若遇到的是右括号)
则依次弹出s1
中的运算符并压入s2
,直到遇到右括号为止,并将一对括号丢弃 - 将
s1
剩余栈压入s2
s2
中pop
出的元素的逆序即中缀表达式转后缀表达式的结果
辅助方法
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())
}
Views: 1,826 · Posted: 2021-01-28
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...