计算部分cal.go
package main
// token :数字，+,-,*,/,换行符(\n)忽略
// 先乘除再加减，乘除的优先级大于加减
// 文法
//
// A->MD
// M->数字N
//
// N->*数字N|/数字N
// D->+MD|-MD
// 计算
func calA(A *TreeA) int {
if A == nil {
return 0
}
m := calM(A.M)
total := calD(m, A.D)
return total
}
func calM(M *TreeM) int {
if M == nil {
return 0
}
total := calN(M.Num, M.N)
return total
}
func calD(m int, D *TreeD) int {
if D == nil {
return m
}
if D.Op == OpPlus {
m += calM(D.M)
}
if D.Op == OpSub {
m -= calM(D.M)
}
m = calD(m, D.D)
return m
}
func calN(m int, N *TreeN) int {
if N == nil {
return m
}
for next := N; next != nil; next = next.N {
if next.Op == OpMul {
m *= next.Num
}
if next.Op == OpDiv {
m /= next.Num
}
}
return m
}
main.go
package main
import (
"fmt"
"os"
)
var data []byte
var level int
func main() {
var err error
data, err = os.ReadFile(os.Args[1])
if err != nil {
panic(err)
}
treeA := parseA()
result := calA(treeA)
fmt.Println(result)
}
语法树解析parse.go
package main
import "fmt"
func charConvertToNum(data []byte) int {
var num int
for i := 0; i < len(data); i++ {
charToNum := data[i] - charZero
num = num*10 + int(charToNum)
}
return num
}
// 文法
// A->MD
// M->数字N
// N->*数字N|/数字N
// D->+MD|-MD
func parseA() *TreeA {
printLevel("A", level, "")
level++
getNextToken()
treeM := parseM()
treeD := parseD()
treeA := &TreeA{
M: treeM,
D: treeD,
}
return treeA
}
// 文法
//
// A->MD
// M->数字N
//
// N->*数字N|/数字N
// D->+MD|-MD
func parseM() *TreeM {
expectToken(TokenNumber)
num := charConvertToNum(currentTokenValue)
printLevel("M", level, currentTokenStr)
level++
getNextToken()
treeN := parseN()
var treeM = &TreeM{
Num: num,
N: treeN,
}
return treeM
}
// 文法
//
// A->MD
// M->数字N
//
// N->*数字N|/数字N
// D->+MD|-MD
func parseN() *TreeN {
var op int
var tokenStr string
switch currentToken {
case TokenMul:
op = OpMul
case TokenDiv:
op = OpDiv
default:
return nil
}
tokenStr += currentTokenStr
getNextToken()
expectToken(TokenNumber)
num := charConvertToNum(currentTokenValue)
tokenStr += currentTokenStr
printLevel("N", level, tokenStr)
getNextToken()
N := parseN()
treeN := &TreeN{
Op: op,
Num: num,
N: N,
}
return treeN
}
var tokenDes = map[int]string{
TokenNumber: "数字",
TokenPlus: "加号",
TokenSub: "减号",
TokenMul: "乘号",
TokenDiv: "除号",
}
// 文法
//
// A->MD
// M->数字N
//
// N->*数字N|/数字N
// D->+MD|-MD
func parseD() *TreeD {
var op int
switch currentToken {
case TokenPlus:
op = OpPlus
case TokenSub:
op = OpSub
case TokenMul, TokenDiv, TokenNumber:
panic(fmt.Errorf("要么是加，要么是减，要么不是token,不能是乘，除，数字，currentToken:%s,currentTokenStr:%s,line:%d,column%d", tokenDes[currentToken], currentTokenStr, currenLine, currenColumn))
case TokenEnd:
fmt.Println("解析结束")
return nil
}
printLevel("D", level, currentTokenStr)
level++
getNextToken()
M := parseM()
D := parseD()
treeD := &TreeD{
Op: op,
M: M,
D: D,
}
return treeD
}
token部分 token.go
package main
import "fmt"
// 词法
// token : +,-,*,/,数字
// \n,空格忽略
// 文法
// A->MD
// M->数字N
// N->*数字N|/数字N
// D->+MD|-MD
const (
TokenNumber = 0
TokenPlus = 1
TokenSub = 2
TokenMul = 3
TokenDiv = 4
TokenEnd = 5
)
// 48, 49, 50, 51, 52, 53, 54, 55, 56, 57 对应数字0,1,2,3,4,5,6,7,8,9
// 空格
// + ，-，*，/
// 换行符号
const (
charZero = 48
charOne = 49
charTwo = 50
charThree = 51
charFour = 52
charFive = 53
charSix = 54
charSeven = 55
charEight = 56
charNine = 57
charEmpty = 32 //空格
charPlus = 43 // +
charSub = 45 //-
charMul = 42 //*
charDiv = 47 // /
charWrap = 10 //换行\n
charEOF = 111 //没有字符了
)
var currentToken int
var currentTokenStr string
var currenLine int = 1
var currenColumn int = 0
var preColumn int = 0
var prevLine int = 1
var currentChar byte
var currentTokenValue []byte
// var currenChar int
var currentDataPoint = -1
func printLevel(parseName string, level int, token string) {
var s = ""
for i := 0; i < level; i++ {
s += "\t"
}
fmt.Printf("%sparseName=%s,token=%s\n", s, parseName, token)
}
func backChar() {
currenLine = prevLine
currenColumn = preColumn
currentDataPoint--
if currentDataPoint >= 0 && currentDataPoint <= len(data) {
currentChar = data[currentDataPoint]
}
}
// 获取下一个字符
func getNextChar() {
preColumn = currenColumn
prevLine = currenLine
currentDataPoint++
if currentDataPoint >= len(data) {
currentChar = charEOF
return
}
currentChar = data[currentDataPoint]
switch currentChar {
case charWrap:
currenLine++
currenColumn = 0
default:
currenColumn++
}
}
func getNextToken() {
for {
getNextChar()
switch currentChar {
case charEOF:
currentToken = TokenEnd
return
case charEmpty: // 空字符
currentTokenStr = ""
case charWrap: //\n换行
currentTokenStr = "\n"
case charZero:
currentTokenStr = "0"
currentToken = TokenNumber
return
case charOne, charTwo, charThree, charFour, charFive, charSix, charSeven, charEight, charNine: // 1-9
currentTokenStr = ""
currentTokenStr += string(currentChar)
var charArr []byte
charArr = append(charArr, currentChar)
for {
getNextChar()
switch currentChar {
case charZero, charOne, charTwo, charThree, charFour, charFive, charSix, charSeven, charEight, charNine: //数字
currentTokenStr += string(currentChar)
charArr = append(charArr, currentChar)
case charWrap:
default:
currentTokenValue = charArr
backChar()
currentToken = TokenNumber
return
}
}
case charPlus: // +
currentToken = TokenPlus
currentTokenStr = "+"
return
case charSub: // -
currentToken = TokenSub
currentTokenStr = "-"
return
case charMul: // *
currentToken = TokenMul
currentTokenStr = "*"
return
case charDiv: // /
currentToken = TokenDiv
currentTokenStr = "/"
return
default:
errMsg, _ := fmt.Printf("非法的字符%c,在第%d行，%d列", data[currentDataPoint], currenLine, currenColumn)
panic(errMsg)
}
}
}
func expectToken(token int) {
if currentToken != token {
errmsg, _ := fmt.Printf("期望%s,实际%s,错误的字符串%s,所在行%d,所在列%d", tokenDes[token], tokenDes[currentToken], currentTokenStr, currenLine, currenColumn)
panic(errmsg)
}
}
树结构体部分tree.go
package main
const (
OpPlus = 1
OpSub = 2
OpMul = 3
OpDiv = 4
)
// 文法
//
// A->MD
// M->数字N
//
// N->*数字N|/数字N
// D->+MD|-MD
type TreeA struct {
M *TreeM
D *TreeD
}
type TreeM struct {
Num int
N *TreeN
}
type TreeN struct {
Op int
Num int
N *TreeN
}
type TreeD struct {
Op int
M *TreeM
D *TreeD
}
过程就是先根据一个个token生成一颗语法树，然后解析语法树木，计算最终结果
