中缀表达式转前缀表达式并计算

什么是中缀表达式、前缀表达式

在计算机科学和数学逻辑中，中缀表达式（Infix Expression）和前缀表达式（Prefix Expression）是两种不同的算术或逻辑公式表示方法。
它们的核心区别在于运算符（如 +, -, *, /）相对于操作数（如数字或变量）的位置

一、中缀表达式 (Infix Expression)

概念

这是我们最熟悉、最符合人类思维习惯的表达方式。

定义：运算符位于两个操作数中间。

形式：<操作数A> <运算符> <操作数B>

示例：
- 3 + 4
- A * (B + C)
优点

依赖优先级：计算机在处理时，必须知道乘除法优先于加减法。

依赖括号：为了改变运算顺序，必须使用括号。例如 2 + 3 * 4 结果是 14，而 (2 + 3) * 4 结果是 20。
用途

人类交互：由于符合直觉，它是所有主流编程语言（C, Java, Python等）和数学教科书中编写公式的标准格式。

源代码编写：程序员编写代码时使用中缀表达式。

二、前缀表达式 (Prefix Expression)

概念

也称为波兰表达式（Polish Notation），由波兰逻辑学家 Jan Łukasiewicz 发明。

定义：运算符位于两个操作数之前。

形式：<运算符> <操作数A> <操作数B>

示例：
- 中缀 3 + 4 $\rightarrow$ 前缀 + 3 4
- 中缀 (2 + 3) * 4 $\rightarrow$ 前缀 * + 2 3 4
特点

无括号：这是前缀表达式最大的特点。因为它由运算符的位置自然决定了运算顺序，不需要括号来消除歧义。

求值顺序：
- 计算机视角：通常从右向左扫描。遇到数字压入栈，遇到运算符则弹出栈顶的两个数字进行计算，将结果压入栈。
- 树的视角：前缀表达式对应于表达式树（Expression Tree）的前序遍历（Pre-order Traversal）。
用途

计算机解析（Parsing）：相比中缀表达式，前缀表达式更容易被计算机解析，因为它消除了处理运算符优先级和括号匹配的复杂性。

函数式编程：Lisp 语言（及其方言 Scheme, Racket, Clojure）的代码本质上就是前缀表达式。
- Lisp 例子：(+ 1 2) 表示 1 + 2。
- 编译器设计：在构建抽象语法树（AST）时，节点通常是以操作符为根，操作数为子节点，这本质上是一种前缀结构的体现。

三、Go实现中缀表达式转前缀表达式并计算

// convert.go

package main

import (
	"strconv"
	"strings"
)

// 定义运算符的优先级
var precedence = map[string]int{
	"+": 1,
	"-": 1,
	"*": 2,
	"/": 2,
}

// 中缀表达式转前缀表达式
func infixToPrefix(infixExpr string) (string, error) {
	// 将中缀表达式转换为逆序的切片
	reversedTokens := reverseTokens(tokenize(infixExpr))

	// 栈用于保存运算符
	var operatorStack []string
	// 结果字符串
	result := ""

	for _, token := range reversedTokens {
		if isOperand(token) {
			// 如果是操作数，直接添加到结果字符串
			result += token + " "
		} else if token == ")" {
			// 如果是右括号，入栈
			operatorStack = append(operatorStack, token)
		} else if token == "(" {
			// 如果是左括号，弹出栈中的运算符并添加到结果字符串，直到遇到右括号
			for len(operatorStack) > 0 && operatorStack[len(operatorStack)-1] != ")" {
				result += string(operatorStack[len(operatorStack)-1]) + " "
				operatorStack = operatorStack[:len(operatorStack)-1]
			}
			// 弹出右括号
			operatorStack = operatorStack[:len(operatorStack)-1]
		} else {
			// 如果是运算符，比较优先级
			for len(operatorStack) > 0 && precedence[token] < precedence[operatorStack[len(operatorStack)-1]] {
				result += string(operatorStack[len(operatorStack)-1]) + " "
				operatorStack = operatorStack[:len(operatorStack)-1]
			}
			// 当前运算符入栈
			operatorStack = append(operatorStack, token)
		}
	}

	// 将栈中剩余的运算符添加到结果字符串
	for len(operatorStack) > 0 {
		result += string(operatorStack[len(operatorStack)-1]) + " "
		operatorStack = operatorStack[:len(operatorStack)-1]
	}

	// 去掉最后的空格并翻转结果字符串
	result = strings.TrimSpace(result)
	return reverseString(result), nil
}

// 将字符串逆序
func reverseString(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

// 将表达式字符串分割成运算符和操作数的切片
func tokenize(expr string) []string {
	var tokens []string
	token := ""

	for _, char := range expr {
		if isOperator(char) || isParenthesis(char) {
			if token != "" {
				tokens = append(tokens, token)
				token = ""
			}
			tokens = append(tokens, string(char))
		} else if char == ' ' {
			if token != "" {
				tokens = append(tokens, token)
				token = ""
			}
		} else {
			token += string(char)
		}
	}

	if token != "" {
		tokens = append(tokens, token)
	}

	return tokens
}

// 判断是否为运算符
func isOperator(char rune) bool {
	return char == '+' || char == '-' || char == '*' || char == '/'
}

// 判断是否为括号
func isParenthesis(char rune) bool {
	return char == '(' || char == ')'
}

// 判断是否为操作数
func isOperand(token string) bool {
	_, err := strconv.Atoi(token)
	return err == nil
}

// 将切片逆序
func reverseTokens(tokens []string) []string {
	for i, j := 0, len(tokens)-1; i < j; i, j = i+1, j-1 {
		tokens[i], tokens[j] = tokens[j], tokens[i]
	}
	return tokens
}

// 计算前缀表达式
func evalPrefix(prefix string) (int, error) {
	tokens := strings.Fields(prefix)
	stack := make([]int, 0)

	for i := len(tokens) - 1; i >= 0; i-- {
		token := tokens[i]

		// 如果是操作数，入栈
		if isOperand(token) {
			num, err := strconv.Atoi(token)
			if err != nil {
				return 0, err
			}
			stack = append(stack, num)
		} else {
			// 如果是运算符，从栈中弹出相应数量的操作数进行计算
			operand1 := stack[len(stack)-1]
			operand2 := stack[len(stack)-2]
			stack = stack[:len(stack)-2]

			switch token {
			case "+":
				stack = append(stack, operand1+operand2)
			case "-":
				stack = append(stack, operand1-operand2)
			case "*":
				stack = append(stack, operand1*operand2)
			case "/":
				stack = append(stack, operand1/operand2)
			}
		}
	}

	// 最终栈中剩余的元素即为计算结果
	if len(stack) != 1 {
		return 0, fmt.Errorf("invalid prefix expression")
	}

	return stack[0], nil
}

四、运行结果

// main.go

package main

import (
  "fmt"
)

func main() {
	infixExpr := "1+2*(3+4)+1"
	prefixExpr, err := infixToPrefix(infixExpr)

	if err != nil {
		fmt.Println("Error:", err)
	} else {
		fmt.Println("Infix Expression:", infixExpr)
		fmt.Println("Prefix Expression:", prefixExpr)
	}

	prefix, _ := evalPrefix(prefixExpr)

	fmt.Println("result", prefix)
}