Go 语言表达式求值器
一、概述
表达式求值器是一类常见的计算机程序,它可以解析字符串表达式,求出表达式的值。本文将介绍如何使用 Go 语言来实现一个表达式求值器。
主要内容包括:
- 表达式求值器介绍
- 需求分析
- 总体设计
- 词法解析
- 语法解析
- 求值计算
- 测试用例
- 扩展实现
- 总结
希望通过本文可以让读者了解如何使用 Go 语言实现一个简单的表达式求值器。
二、表达式求值器介绍
表达式求值器可以接受一个字符串表达式,对其求值后返回结果。
例如输入表达式:"1 + 2",求值器会计算出结果 3。
表达式中常见的可计算元素包括:
- 数字:1, 2.5, 3.14 等
- 变量:x, y, z 等
- 运算符:+ - * /等
- 函数:abs(), max()等
- 括号表示优先级:(...)
一个完整的表达式求值器还需要支持更多特性,比如函数调用、更多的数据类型等。
三、需求分析
需要实现一个简单的算术表达式求值器,具有如下功能需求:
- 支持整数浮点数
- 支持+ - * /运算
- 支持小括号表示优先级
- 支持变量
- 可以扩展新的运算符
输入一个表达式,输出求值结果。
四、总体设计
表达式求值可以分为以下步骤:
- 词法分析:将表达式字符串分解成词法单元(数字、符号、变量等)
- 语法分析:构建语法树
- 求值:对语法树进行运算求值
五、词法分析
词法分析将字符串表达式分割为词法单元,也就是编程语言中最小的语义单位,常见的词法单元有:
- 数字:1, 1.2, .3, 3.14
- 运算符:+ - * /
- 括号:( )
- 变量:x y z
- 分隔符:, ; 等
package main import ( "fmt" "regexp" ) func main() { pattern := `\d+|\w+|[\*\+\-\(\)]` lex := regexp.MustCompile(pattern) tokens := lex.FindAllString("1 + (2 - 3) * 4", -1) fmt.Println("Tokens:") for _, token := range tokens { fmt.Println(token) } }
六、语法解析
在词法分析的基础上,使用递归下降解析方法构建语法树。
递归下降解析是一种非常简单和常见的语法解析方法。
递归下降解析器的工作可以分解为以下步骤:
- 如果遇到终结符(数字、变量等),返回终结符
- 对于运算符,匹配运算优先级,构造语法树节点
- 使用递归调用继续解析剩余表达式
递归下降解析不需要单独的栈,通过函数调用栈实现解析。
七、求值计算
有了语法树后,可以递归遍历语法树,进行求值计算。
对树节点进行运算求值:
- 叶子节点是数字或变量,直接返回值
- 一元运算符节点,计算子节点的值
- 二元运算符,计算左右子节点的值
- 返回根节点的值
通过递归求值,可以处理所有复杂的嵌套计算。
八、测试用例
编写表达式测试用例,covering 不同的语法场景
package main import ( "bufio" "fmt" "os" "strconv" "strings" ) // Node 结构表示解析树的节点 type Node struct { Left, Right *Node // 左右子节点 Op string // 操作符（+、-、*、/）或空字符串（叶子节点） Val int // 叶子节点的值 } // parse 函数接受一个字符串数组 tokens，返回解析后的根节点 func parse(tokens []string) *Node { var index int return parseExpression(tokens, &index) } // parseExpression 解析加法和减法表达式 func parseExpression(tokens []string, index *int) *Node { left := parseTerm(tokens, index) // 处理加法和减法运算符 for *index < len(tokens) && (tokens[*index] == "+" || tokens[*index] == "-") { op := tokens[*index] (*index)++ right := parseTerm(tokens, index) left = &Node{Left: left, Right: right, Op: op} } return left } // parseTerm 解析乘法和除法表达式 func parseTerm(tokens []string, index *int) *Node { left := parseFactor(tokens, index) // 处理乘法和除法运算符 for *index < len(tokens) && (tokens[*index] == "*" || tokens[*index] == "/") { op := tokens[*index] (*index)++ right := parseFactor(tokens, index) left = &Node{Left: left, Right: right, Op: op} } return left } // parseFactor 解析数字或括号内的表达式 func parseFactor(tokens []string, index *int) *Node { token := tokens[*index] (*index)++ if token == "(" { // 如果遇到左括号，递归解析括号内的表达式 node := parseExpression(tokens, index) if tokens[*index] != ")" { panic("Expected closing parenthesis") } (*index)++ return node } // 如果是数字，创建一个叶子节点 val, err := strconv.Atoi(token) if err != nil { panic("Invalid number") } return &Node{Val: val} } // evaluate 函数计算解析树的值 func evaluate(node *Node) int { if node.Op == "" { // 叶子节点，返回其值 return node.Val } // 递归计算左右子树的值 leftValue := evaluate(node.Left) rightValue := evaluate(node.Right) // 根据操作符执行相应的运算 switch node.Op { case "+": return leftValue + rightValue case "-": return leftValue - rightValue case "*": return leftValue * rightValue case "/": if rightValue == 0 { panic("Division by zero") } return leftValue / rightValue default: panic("Unknown operator: " + node.Op) } } func main() { reader := bufio.NewReader(os.Stdin) // 循环等待用户输入表达式 for { fmt.Print("输入一个表达式（或输入'exit'退出）：") input, _ := reader.ReadString('\n') input = strings.TrimSpace(input) if input == "exit" { break } // 将输入的字符串分割为单词 tokens := strings.Fields(input) // 解析并计算表达式的值 ast := parse(tokens) result := evaluate(ast) // 输出计算结果 fmt.Println("Result:", result) } }
并验证求值器求出的结果是否正确。
九、扩展实现
可以针对求值器进行各种扩展:
- 支持更多数据类型:字符串、布尔值等
- 扩展运算符:- 加法、取余数等
- 支持函数调用:abs(), max()等
- 支持变量赋值运算
- 更强大的语法分析模块
总结
本文介绍了如何使用 Go 语言实现一个简单的表达式求值器。涵盖了词法解析、语法解析和求值计算三个关键模块。可以作为编写解释器和编译器的基础。
通过扩展求值器的运算符和语法，可以得到一个功能更丰富的计算平台。
