面试题：Go操作符优先级在复杂场景下的应用

Question

假设你正在开发一个Go语言的表达式解析器，表达式中可能包含各种Go语言支持的操作符，如算术操作符、逻辑操作符、位操作符等。请设计一个算法或数据结构，能够正确解析并按照Go语言操作符优先级规则计算任意给定的复杂表达式的值。可以用伪代码或Go代码框架进行描述，并说明关键步骤和处理优先级的方式。

Answer 1

1. 使用栈的思路：
   • 利用两个栈，一个用于操作数（operandStack），一个用于操作符（operatorStack）。
   • 遍历表达式，对于数字字符，将其解析为操作数并压入operandStack；对于操作符，根据其优先级与operatorStack栈顶操作符比较。
   • 如果当前操作符优先级高于栈顶操作符或operatorStack为空，将当前操作符压入operatorStack；否则，从operandStack弹出两个操作数，从operatorStack弹出一个操作符，进行计算，并将结果压入operandStack，重复此过程直到当前操作符可以压入operatorStack。
   • 遇到左括号(直接压入operatorStack，遇到右括号)则持续从operandStack弹出两个操作数，从operatorStack弹出一个操作符进行计算，直到遇到左括号(，并将左括号从operatorStack弹出。
   • 遍历结束后，依次从operandStack弹出两个操作数，从operatorStack弹出一个操作符进行计算，直到operatorStack为空，此时operandStack中的唯一元素即为表达式的结果。
2. Go代码框架示例：

package main

import (
    "fmt"
    "strconv"
)

// 定义操作符优先级
var precedence = map[string]int{
    "+": 1,
    "-": 1,
    "*": 2,
    "/": 2,
    "%": 2,
    "&": 3,
    "|": 3,
    "^": 3,
    "&&": 4,
    "||": 4,
}

func evaluateExpression(expression string) int {
    var operandStack []int
    var operatorStack []string

    for i := 0; i < len(expression); {
        if expression[i] >= '0' && expression[i] <= '9' {
            num := 0
            for ; i < len(expression) && expression[i] >= '0' && expression[i] <= '9'; i++ {
                num = num*10 + int(expression[i]-'0')
            }
            operandStack = append(operandStack, num)
            i--
        } else if expression[i] == '(' {
            operatorStack = append(operatorStack, string(expression[i]))
        } else if expression[i] == ')' {
            for len(operatorStack) > 0 && operatorStack[len(operatorStack)-1] != "(" {
                operand2 := operandStack[len(operandStack)-1]
                operand1 := operandStack[len(operandStack)-2]
                operator := operatorStack[len(operatorStack)-1]
                result := applyOperator(operand1, operand2, operator)
                operandStack = operandStack[:len(operandStack)-2]
                operatorStack = operatorStack[:len(operatorStack)-1]
                operandStack = append(operandStack, result)
            }
            operatorStack = operatorStack[:len(operatorStack)-1]
        } else {
            operator := string(expression[i])
            for len(operatorStack) > 0 && operatorStack[len(operatorStack)-1] != "(" && precedence[operatorStack[len(operatorStack)-1]] >= precedence[operator] {
                operand2 := operandStack[len(operandStack)-1]
                operand1 := operandStack[len(operandStack)-2]
                operator := operatorStack[len(operatorStack)-1]
                result := applyOperator(operand1, operand2, operator)
                operandStack = operandStack[:len(operandStack)-2]
                operatorStack = operatorStack[:len(operatorStack)-1]
                operandStack = append(operandStack, result)
            }
            operatorStack = append(operatorStack, operator)
        }
        i++
    }

    for len(operatorStack) > 0 {
        operand2 := operandStack[len(operandStack)-1]
        operand1 := operandStack[len(operandStack)-2]
        operator := operatorStack[len(operatorStack)-1]
        result := applyOperator(operand1, operand2, operator)
        operandStack = operandStack[:len(operandStack)-2]
        operatorStack = operatorStack[:len(operatorStack)-1]
        operandStack = append(operandStack, result)
    }

    return operandStack[0]
}

func applyOperator(operand1, operand2 int, operator string) int {
    switch operator {
    case "+":
        return operand1 + operand2
    case "-":
        return operand1 - operand2
    case "*":
        return operand1 * operand2
    case "/":
        return operand1 / operand2
    case "%":
        return operand1 % operand2
    case "&":
        return operand1 & operand2
    case "|":
        return operand1 | operand2
    case "^":
        return operand1 ^ operand2
    case "&&":
        if operand1 != 0 && operand2 != 0 {
            return 1
        }
        return 0
    case "||":
        if operand1 != 0 || operand2 != 0 {
            return 1
        }
        return 0
    }
    return 0
}

3. 关键步骤总结：
   • 词法分析：遍历表达式，识别数字、操作符、括号等元素。
   • 操作符优先级处理：通过precedence映射表确定操作符优先级，在遇到操作符时，比较其与operatorStack栈顶操作符优先级，根据规则决定是否进行计算。
   • 括号处理：左括号(直接压入操作符栈，右括号)触发括号内表达式计算。
   • 计算结果：遍历结束后，处理操作符栈剩余操作符，最终操作数栈中唯一元素就是表达式计算结果。