Golang栈结构和后缀表达式实现计算器示例
作者:wuYin 时间:2024-05-02 16:25:09
引言
只进行基本的四则运算,利用栈结构和后缀表达式来计算数学表达式的值。
本文代码:GitHub
运行效果:
问题
如果只能进行两个值的加减乘除,如何编程计算一个数学表达式的值?
比如计算 1+2*3+(4*5+6)*7
,我们知道优先级顺序 ()
大于 * /
大于 + -
,直接计算得 1+6+26*7 = 189
中缀、后缀表达式的计算
人利用中缀表达式计算值
数学表达式的记法分为前缀、中缀和后缀记法,其中中缀就是上边的算术记法: 1+2*3+(4*5+6)*7
,人计算中缀表达式的值:把表达式分为三部分1
2+3
(4*5+6)*7
分别计算值,求和得 189。但这个理解过程在计算机上的实现就复杂了。
计算机利用后缀表达式计算值
中缀表达式 1+2*3+(4*5+6)*7
对应的后缀表达式: 123*+45*6+7*+
,计算机使用栈计算后缀表达式值:
计算后缀表达式的代码实现
func calculate(postfix string) int {
stack := stack.ItemStack{}
fixLen := len(postfix)
for i := 0; i < fixLen; i++ {
nextChar := string(postfix[i])
// 数字:直接压栈
if unicode.IsDigit(rune(postfix[i])) {
stack.Push(nextChar)
} else {
// 操作符:取出两个数字计算值,再将结果压栈
num1, _ := strconv.Atoi(stack.Pop())
num2, _ := strconv.Atoi(stack.Pop())
switch nextChar {
case "+":
stack.Push(strconv.Itoa(num1 + num2))
case "-":
stack.Push(strconv.Itoa(num1 - num2))
case "*":
stack.Push(strconv.Itoa(num1 * num2))
case "/":
stack.Push(strconv.Itoa(num1 / num2))
}
}
}
result, _ := strconv.Atoi(stack.Top())
return result
}
现在只需知道如何将中缀转为后缀,再利用栈计算即可。
中缀表达式转后缀表达式
转换过程
从左到右逐个字符遍历中缀表达式,输出的字符序列即是后缀表达式:
遇到数字直接输出
遇到运算符则判断:
栈顶运算符优先级更低则入栈,更高或相等则直接输出
栈为空、栈顶是
(
直接入栈运算符是
)
则将栈顶运算符全部弹出,直到遇见)
中缀表达式遍历完毕,运算符栈不为空则全部弹出,依次追加到输出
转换的代码实现
// 中缀表达式转后缀表达式
func infix2ToPostfix(exp string) string {
stack := stack.ItemStack{}
postfix := ""
expLen := len(exp)
// 遍历整个表达式
for i := 0; i < expLen; i++ {
char := string(exp[i])
switch char {
case " ":
continue
case "(":
// 左括号直接入栈
stack.Push("(")
case ")":
// 右括号则弹出元素直到遇到左括号
for !stack.IsEmpty() {
preChar := stack.Top()
if preChar == "(" {
stack.Pop() // 弹出 "("
break
}
postfix += preChar
stack.Pop()
}
// 数字则直接输出
case "0", "1", "2", "3", "4", "5", "6", "7", "8", "9":
j := i
digit := ""
for ; j < expLen && unicode.IsDigit(rune(exp[j])); j++ {
digit += string(exp[j])
}
postfix += digit
i = j - 1 // i 向前跨越一个整数,由于执行了一步多余的 j++,需要减 1
default:
// 操作符:遇到高优先级的运算符,不断弹出,直到遇见更低优先级运算符
for !stack.IsEmpty() {
top := stack.Top()
if top == "(" || isLower(top, char) {
break
}
postfix += top
stack.Pop()
}
// 低优先级的运算符入栈
stack.Push(char)
}
}
// 栈不空则全部输出
for !stack.IsEmpty() {
postfix += stack.Pop()
}
return postfix
}
// 比较运算符栈栈顶 top 和新运算符 newTop 的优先级高低
func isLower(top string, newTop string) bool {
// 注意 a + b + c 的后缀表达式是 ab + c +,不是 abc + +
switch top {
case "+", "-":
if newTop == "*" || newTop == "/" {
return true
}
case "(":
return true
}
return false
}
来源:https://segmentfault.com/a/1190000013126678
标签:Golang,计算器,栈结构,后缀表达式
0
投稿
猜你喜欢
浅谈pytorch池化maxpool2D注意事项
2023-07-14 15:02:30
MySQL与PHP的基础与应用专题之数据查询
2023-11-10 10:09:55
kafka监控获取指定topic的消息总量示例
2023-09-04 01:44:48
pytest官方文档解读fixtures的autouse
2023-06-22 01:18:58
Ubuntu下mysql与mysql workbench安装教程
2024-01-14 23:08:40
vue单页面打包文件大?首次加载慢?nginx带你飞,从7.5M到1.3M蜕变过程(推荐)
2024-05-28 15:54:41
Python数据分析之pandas比较操作
2021-11-23 05:14:22
通过js获取上传的图片信息(临时保存路径,名称,大小)然后通过ajax传递给后端的方法
2024-04-17 10:06:38
python列表[list]和元组(tuple)详情
2022-05-23 01:14:31
python简单实现获取当前时间
2022-08-28 16:38:49
Win7 x64 IIS运行ASP+Access故障完美解决方法(转)
2012-03-27 18:30:35
浅析Vue自定义组件的v-model
2024-04-29 13:10:16
Python DataFrame使用drop_duplicates()函数去重(保留重复值,取重复值)
2023-09-29 20:42:35
SQL SERVER数据库开发之asp存储过程应用
2008-05-19 12:55:00
Vue实现简单跑马灯特效
2024-04-30 10:31:05
python使用htmllib分析网页内容的方法
2022-05-22 13:28:33
Matplotlib控制坐标轴刻度间距与标签实例代码
2022-01-26 03:47:39
django创建超级用户时指定添加其它字段方式
2022-08-13 17:24:18
pytorch+lstm实现的pos示例
2023-08-11 22:02:10
mysql unsigned 用法及相减出现补数溢出解决方法
2024-01-22 19:26:53