Go语言利用栈结构实现中缀转后缀表达式计算器

问题背景

如果编程环境只支持简单的两个值加减乘除，如何计算如 1+2*3+(4*5+6)*7 这样包含多优先级运算符的复杂数学表达式？

人类可以直接根据括号和运算优先级顺序得出结果（本例为 189），但计算机需要一套标准化的流程来处理这种层级关系。通常的做法是将“中缀表达式”转换为“后缀表达式”，再利用栈进行统一计算。

基础概念：前缀、中缀与后缀

中缀表达式的局限

我们日常使用的算术记法称为中缀表达式，例如：1+2*3。虽然人类能直观地识别先乘除后加减的规则，但这种结构对于计算机而言，处理优先级嵌套和括号匹配较为复杂。

计算机为何使用后缀表达式

后缀表达式（Reverse Polish Notation）去除了括号，且运算符位于操作数之后。例如上述中缀表达式对应的后缀形式为：123*+45*6+7*。

计算机只需从左到右扫描后缀表达式，遇到数字压入栈中，遇到运算符则弹出栈顶的两个数字进行计算，并将结果重新压入栈中。最后栈中剩余的唯一元素即为最终结果。

步骤一：计算后缀表达式

在实现转换之前，我们先看如何利用栈计算已知后缀表达式的值。这是一个典型的“后进先出”应用场景。

// calculate 接收后缀表达式字符串并返回计算结果
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
}

步骤二：中缀转后缀表达式

这是计算器实现的难点。我们需要维护一个运算符栈，按照特定规则将中缀表达式中的字符转化为后缀序列。

转换规则

1. 数字：直接输出到后缀表达式。
2. 左括号 (：直接压入运算符栈。
3. 右括号 )：不断弹出栈顶运算符并追加到后缀表达式，直到遇到左括号为止（左括号弹出但不输出）。
4. 运算符：

• 如果栈为空，或栈顶是左括号 (，直接入栈。
• 如果当前运算符优先级 高于 栈顶运算符，直接入栈。
• 如果当前运算符优先级 低于或等于 栈顶运算符，则弹出栈顶运算符并追加到后缀表达式，重复判断直到满足入栈条件。
• 注意：加减乘除同级，遵循从左到右结合性。

转换代码实现

// infix2ToPostfix 将中缀表达式转换为后缀表达式
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
}

// isLower 比较运算符栈栈顶 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
}

总结

通过上述代码，我们可以构建一个基础的Go语言计算器。整个流程清晰地展示了如何将复杂的人阅读习惯（中缀）转化为计算机易于处理的线性序列（后缀），核心都依赖于栈的数据结构特性。

以上就是利用Go语言栈结构和后缀表达式实现计算器的详细内容，更多关于Go语言算法与数据结构计算的资料请关注本站其它相关文章！