Go語言中怎么實現(xiàn)一個表達(dá)式求值器,針對這個問題,這篇文章詳細(xì)介紹了相對應(yīng)的分析和解答,希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),井陘企業(yè)網(wǎng)站建設(shè),井陘品牌網(wǎng)站建設(shè),網(wǎng)站定制,井陘網(wǎng)站建設(shè)報價,網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,井陘網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè),幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力??沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿,時刻以成就客戶成長自我,堅持不斷學(xué)習(xí)、思考、沉淀、凈化自己,讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。
開始,先確定要使用一個接口 Expr 來代表這種語言的任意一個表達(dá)式。暫時沒有任何方法,稍后再逐個添加:
// Expr: 算術(shù)表達(dá)式 type Expr interface{}
我們的表達(dá)式語言將包括以下符號:
浮點數(shù)字面量
二元操作符:加減乘除(+、-、*、\/)
一元操作符:表示正數(shù)和負(fù)數(shù)的 -x 和 +x
函數(shù)調(diào)用:pow(x,y)、sin(x) 和 sqrt(x)
變量:比如 x、pi,自己定義一個變量名稱,每次可以提供不用的值
還要有標(biāo)準(zhǔn)的操作符優(yōu)先級,以及小括號。所有的值都是 float64 類型。
下面是幾個示例表達(dá)式:
sqrt(A / pi) pow(x, 3) + pow(y, 3) (F - 32) * 5 / 9
下面5種具體類型代表特定類型的表達(dá)式:
Var : 代表變量引用。這個類型是可導(dǎo)出的,至于為什么,后面會講明
literal : 代表浮點數(shù)常量
unary : 代表有一個操作數(shù)的操作符表達(dá)式,操作數(shù)可以是任意的 Expr
binary : 代表有兩個操作數(shù)的操作符表達(dá)式,操作數(shù)可以是任意的 Expr
call : 代表函數(shù)調(diào)用,這里限制它的 fn 字段只能是 pow、sin、sqrt
為了要計算包含變量的表達(dá)式,還需要一個上下文(environment)來把變量映射到數(shù)值。所有接口和類型的定義如下:
package eval // Expr: 算術(shù)表達(dá)式 type Expr interface { // 返回表達(dá)式在 env 上下文下的值 Eval(env Env) float64 // Check 方法報告表達(dá)式中的錯誤,并把表達(dá)式中的變量加入 Vars 中 Check(vars map[Var]bool) error } // Var 表示一個變量,比如:x. type Var string // Env 變量到數(shù)值的映射關(guān)系 type Env map[Var]float64 // literal 是一個數(shù)字常量,比如:3.1415926 type literal float64 // unary 表示一元操作符表達(dá)式,比如:-x type unary struct { op rune // one of '+', '-' x Expr } // binary 表示二元操作符表達(dá)式,比如:x+y. type binary struct { op rune // one of '+', '-', '*', '/' x, y Expr } // call 表示函數(shù)調(diào)用表達(dá)式,比如:sin(x). type call struct { fn string // one of "pow", "sin", "sqrt" args []Expr }
在定義好各種類型后,發(fā)現(xiàn)每個類型都需要提供一個 Eval 方法,于是加把這個方法加到接口中,已經(jīng)添加到上面的代碼中了。
這個包只導(dǎo)出了 Expr、Var、Env??蛻舳丝梢栽诓唤佑|其他表達(dá)式類型的情況下使用這個求值器。
接下來實現(xiàn)每個類型的 Eval 方法來滿足接口:
Var 的 Eval 方法從上下文中查詢結(jié)果,如果變量不存在,則會返回0。
literal 的 Eval 方法直接返回本身的值。
unbary 的 Eval 方法首先對操作數(shù)遞歸求值,然后應(yīng)用 op 操作符。
binary 的 Eval 方法的處理邏輯和 unbary 一樣。
call 的 Eval 方法先對 pow、sin、sqrt 函數(shù)的參數(shù)求值,再調(diào)用 math 包中的對應(yīng)函數(shù)。
package eval import ( "fmt" "math" ) func (v Var) Eval(env Env) float64 { return env[v] // 如果查詢不到變量名,則返回類型的零值,就是0 } func (l literal) Eval(_ Env) float64 { return float64(l) } func (u unary) Eval(env Env) float64 { switch u.op { case '+': return +u.x.Eval(env) case '-': return -u.x.Eval(env) } panic(fmt.Sprintf("unsupported unary operator: %q", u.op)) } func (b binary) Eval(env Env) float64 { switch b.op { case '+': return b.x.Eval(env) + b.y.Eval(env) case '-': return b.x.Eval(env) - b.y.Eval(env) case '*': return b.x.Eval(env) * b.y.Eval(env) case '/': return b.x.Eval(env) / b.y.Eval(env) } panic(fmt.Sprintf("unsupported binary operator: %q", b.op)) } func (c call) Eval(env Env) float64 { switch c.fn { case "pow": return math.Pow(c.args[0].Eval(env), c.args[1].Eval(env)) case "sin": return math.Sin(c.args[0].Eval(env)) case "sqrt": return math.Sqrt(c.args[0].Eval(env)) } panic(fmt.Sprintf("unsupported function call: %s", c.fn)) }
某些方法可能會失敗,有些錯誤會導(dǎo)致 Eval 崩潰,還有些會導(dǎo)致返回不正確的結(jié)果。所有這些錯誤可以在求值之前做檢查來發(fā)現(xiàn),所以還需要一個Check方法。不過暫時可以先不管Check方法,而是把 Eval 方法用起來,并通過測試進(jìn)行驗證。
要驗證 Eval 方法,首先需要得到對象,然后調(diào)用對像的 Eval 方法。而對象需要通過解析字符串來獲取,這就需要一個 Parse 函數(shù)。
text/scanner 包的使用
詞法分析器 lexer 使用 text/scanner 包提供的掃描器 Scanner 類型來把輸入流分解成一系列的標(biāo)記(token),包括注釋、標(biāo)識符、字符串字面量和數(shù)字字面量。掃描器的 Scan 方法將提前掃描并返回下一個標(biāo)記(類型為 rune)。大部分標(biāo)記(比如'(')都只包含單個rune,但 text/scanner 包也可以支持由多個字符組成的記號。調(diào)用 Scan 會返回標(biāo)記的類型,調(diào)用 TokenText 則會返回標(biāo)記的文本。
因為每個解析器可能需要多次使用當(dāng)前的記號,但是 Scan 會一直向前掃描,所以把掃描器封裝到一個 lexer 輔助類型中,其中保存了 Scan 最近返回的標(biāo)記。下面是一個簡單的用法示例:
package main import ( "fmt" "os" "strings" "text/scanner" ) type lexer struct { scan scanner.Scanner token rune // 當(dāng)前標(biāo)記 } func (lex *lexer) next() { lex.token = lex.scan.Scan() } func (lex *lexer) text() string { return lex.scan.TokenText() } // consume 方法并沒有被使用到,包括后面的Pause函數(shù) // 不過這是一個可復(fù)用的處理邏輯 func (lex *lexer) consume(want rune) { if lex.token != want { // 注意: 錯誤處理不是這篇的重點,簡單粗暴的處理了 panic(fmt.Sprintf("got %q, want %q", lex.text(), want)) } lex.next() } func main() { for _, input := range os.Args[1:] { lex := new(lexer) lex.scan.Init(strings.NewReader(input)) lex.scan.Mode = scanner.ScanIdents | scanner.ScanInts | scanner.ScanFloats fmt.Println(input, ":") lex.next() for lex.token != scanner.EOF { fmt.Println("\t", scanner.TokenString(lex.token), lex.text()) lex.next() } } }
執(zhí)行效果如下:
PS G:\Steed\Documents\Go\src\localdemo\parse> go run main.go "sqrt(A / pi)" "pow(x, 3) + pow(y, 3)" "(F - 32) * 5 / 9" sqrt(A / pi) : Ident sqrt "(" ( Ident A "/" / Ident pi ")" ) pow(x, 3) + pow(y, 3) : Ident pow "(" ( Ident x "," , Int 3 ")" ) "+" + Ident pow "(" ( Ident y "," , Int 3 ")" ) (F - 32) * 5 / 9 : "(" ( Ident F "-" - Int 32 ")" ) "*" * Int 5 "/" / Int 9 PS G:\Steed\Documents\Go\src\localdemo\parse>
Parse 函數(shù)
Parse 函數(shù),遞歸地將字符串解析為表達(dá)式,下面是完整的代碼:
package eval import ( "fmt" "strconv" "strings" "text/scanner" ) type lexer struct { scan scanner.Scanner token rune // 當(dāng)前標(biāo)記 } func (lex *lexer) next() { lex.token = lex.scan.Scan() } func (lex *lexer) text() string { return lex.scan.TokenText() } type lexPanic string // describe 返回一個描述當(dāng)前標(biāo)記的字符串,用于錯誤處理 func (lex *lexer) describe() string { switch lex.token { case scanner.EOF: return "end of file" case scanner.Ident: return fmt.Sprintf("identifier %s", lex.text()) case scanner.Int, scanner.Float: return fmt.Sprintf("number %s", lex.text()) } return fmt.Sprintf("%q", rune(lex.token)) // any other rune } func precedence(op rune) int { switch op { case '*', '/': return 2 case '+', '-': return 1 } return 0 } // Parse 將字符串解析為表達(dá)式 // // expr = num a literal number, e.g., 3.14159 // | id a variable name, e.g., x // | id '(' expr ',' ... ')' a function call // | '-' expr a unary operator (+-) // | expr '+' expr a binary operator (+-*/) // func Parse(input string) (_ Expr, err error) { defer func() { // 選擇性地使用 recover // 已經(jīng)將 panic value 設(shè)置成特殊類型 lexPanic // 在 recover 時對 panic value 進(jìn)行檢查 switch x := recover().(type) { case nil: // no panic case lexPanic: // 如果發(fā)現(xiàn) panic value 是特殊類型,就將這個 panic 作為 errror 處理 err = fmt.Errorf("%s", x) default: // 如果不是,則按照正常的 panic 進(jìn)行處理 panic(x) } }() lex := new(lexer) lex.scan.Init(strings.NewReader(input)) lex.scan.Mode = scanner.ScanIdents | scanner.ScanInts | scanner.ScanFloats lex.next() // 獲取第一個標(biāo)記 e := parseExpr(lex) if lex.token != scanner.EOF { return nil, fmt.Errorf("unexpected %s", lex.describe()) } return e, nil } func parseExpr(lex *lexer) Expr { return parseBinary(lex, 1) } // binary = unary ('+' binary)* // parseBinary 遇到優(yōu)先級低于 prec1 的運算符時就停止 // 這個遞歸處理計算優(yōu)先級的循環(huán)策略比較難理解 func parseBinary(lex *lexer, prec1 int) Expr { lhs := parseUnary(lex) for prec := precedence(lex.token); prec >= prec1; prec-- { for precedence(lex.token) == prec { op := lex.token lex.next() // consume operator rhs := parseBinary(lex, prec+1) // 優(yōu)先級加1,進(jìn)入下一次遞歸 lhs = binary{op, lhs, rhs} } } return lhs } // unary = '+' expr | primary func parseUnary(lex *lexer) Expr { if lex.token == '+' || lex.token == '-' { op := lex.token lex.next() // consume '+' or '-' return unary{op, parseUnary(lex)} } return parsePrimary(lex) } // primary = id // | id '(' expr ',' ... ',' expr ')' // | num // | '(' expr ')' func parsePrimary(lex *lexer) Expr { switch lex.token { case scanner.Ident: id := lex.text() lex.next() // consume Ident if lex.token != '(' { return Var(id) } lex.next() // consume '(' var args []Expr if lex.token != ')' { for { args = append(args, parseExpr(lex)) if lex.token != ',' { break } lex.next() // consume ',' } if lex.token != ')' { msg := fmt.Sprintf("got %q, want ')'", lex.token) panic(lexPanic(msg)) } } lex.next() // consume ')' return call{id, args} case scanner.Int, scanner.Float: f, err := strconv.ParseFloat(lex.text(), 64) if err != nil { panic(lexPanic(err.Error())) } lex.next() // consume number return literal(f) case '(': lex.next() // consume '(' e := parseExpr(lex) if lex.token != ')' { msg := fmt.Sprintf("got %s, want ')'", lex.describe()) panic(lexPanic(msg)) } lex.next() // consume ')' return e } msg := fmt.Sprintf("unexpected %s", lex.describe()) panic(lexPanic(msg)) }
整體的邏輯都比較難理解。parseBinary 函數(shù)是負(fù)責(zé)解析二元表達(dá)式的,其中包括了對運算符優(yōu)先級的處理(邏輯比較難懂,自己想不出來,看也沒完全看懂,以后有類似的實現(xiàn)或許可以借鑒)。
下面的 TestEval 函數(shù)用于測試求值器,它使用 testing 包,使用基于表的測試方式。表格中定義了三個表達(dá)式并為每個表達(dá)式準(zhǔn)備了不同的上下文。第一個表達(dá)式用于根據(jù)圓面積A求半徑,第二個用于計算兩個變量x和y的立方和,第三個把華氏溫度F轉(zhuǎn)為攝氏溫度:
package eval import ( "fmt" "math" "testing" ) func TestEval(t *testing.T) { tests := []struct { expr string env Env want string }{ {"sqrt(A / pi)", Env{"A": 87616, "pi": math.Pi}, "167"}, {"pow(x, 3) + pow(y, 3)", Env{"x": 12, "y": 1}, "1729"}, {"pow(x, 3) + pow(y, 3)", Env{"x": 9, "y": 10}, "1729"}, {"5 / 9 * (F - 32)", Env{"F": -40}, "-40"}, {"5 / 9 * (F - 32)", Env{"F": 32}, "0"}, {"5 / 9 * (F - 32)", Env{"F": 212}, "100"}, } var prevExpr string for _, test := range tests { // 僅在表達(dá)式變更時才輸出 if test.expr != prevExpr { fmt.Printf("\n%s\n", test.expr) prevExpr = test.expr } expr, err := Parse(test.expr) if err != nil { t.Error(err) // 解析出錯 continue } got := fmt.Sprintf("%.6g", expr.Eval(test.env)) fmt.Printf("\t%v => %s\n", test.env, got) if got != test.want { t.Errorf("%s.Eval() in %v = %q, want %q\n", test.expr, test.env, got, test.want) } } }
對于表格中的每一行記錄,先解析表達(dá)式,在上下文中求值,再輸出表達(dá)式。啟用 -v 選項查看測試的輸出:
PS G:\Steed\Documents\Go\src\gopl\output\expression_evaluator\eval> go test -v === RUN TestEval sqrt(A / pi) map[A:87616 pi:3.141592653589793] => 167 pow(x, 3) + pow(y, 3) map[x:12 y:1] => 1729 map[x:9 y:10] => 1729 5 / 9 * (F - 32) map[F:-40] => -40 map[F:32] => 0 map[F:212] => 100 --- PASS: TestEval (0.00s) PASS ok gopl/output/expression_evaluator/eval 0.329s PS G:\Steed\Documents\Go\src\gopl\output\expression_evaluator\eval>
到目前為止,所有的輸入都是合法的,但是并不是總能如此。即使在解釋性語言中,通過語法檢查來發(fā)現(xiàn)靜態(tài)錯誤(即不用運行程序也能檢測出來的錯誤)也是很常見的。通過分離靜態(tài)檢查和動態(tài)檢查,可以更快發(fā)現(xiàn)錯誤,也可以只在運行前檢查一次,而不用在表達(dá)式求值時每次都檢查。
現(xiàn)在就給 Expr 加上一個 Check 方法,用于在表達(dá)式語法樹上檢查靜態(tài)錯誤。這個 Check 方法有一個 vars 參數(shù),并不是因為需要傳參,而是為了讓遞歸調(diào)用的實現(xiàn)起來更方便,具體看后面的代碼和說明:
// Expr: 算術(shù)表達(dá)式 type Expr interface { // 返回表達(dá)式在 env 上下文下的值 Eval(env Env) float64 // Check 方法報告表達(dá)式中的錯誤,并把表達(dá)式中的變量加入 Vars 中 Check(vars map[Var]bool) error }
具體的 Check 方法如下所示。literal 和 Var 的求值不可能出錯,所以直接返回 nil。unary 和 binary 的方法首先檢查操作符是否合法,再遞歸地檢查操作數(shù)。類似地,call 的方法首先檢查函數(shù)是否是已知的,然后檢查參數(shù)個數(shù),最后遞歸地檢查每個參數(shù):
package eval import ( "fmt" "strings" ) func (v Var) Check(vars map[Var]bool) error { vars[v] = true return nil } func (literal) Check(vars map[Var]bool) error { return nil } func (u unary) Check(vars map[Var]bool) error { if !strings.ContainsRune("+-", u.op) { return fmt.Errorf("unexpected unary op %q", u.op) } return u.x.Check(vars) } func (b binary) Check(vars map[Var]bool) error { if !strings.ContainsRune("+-*/", b.op) { return fmt.Errorf("unexpected binary op %q", b.op) } if err := b.x.Check(vars); err != nil { return err } return b.y.Check(vars) } func (c call) Check(vars map[Var]bool) error { arity, ok := numParams[c.fn] if !ok { return fmt.Errorf("unknown function %q", c.fn) } if len(c.args) != arity { return fmt.Errorf("call to %s has %d args, want %d", c.fn, len(c.args), arity) } for _, arg := range c.args { if err := arg.Check(vars); err != nil { return err } } return nil } // 已知的函數(shù)名稱和對應(yīng)的參數(shù)個數(shù) var numParams = map[string]int{"pow": 2, "sin": 1, "sqrt": 1}
關(guān)于遞歸的實現(xiàn)。Check 的輸入?yún)?shù)是一個 Var 集合,這個集合是表達(dá)式中的變量名。要讓表達(dá)式能成功求值,上下文必須包含所有的變量。從邏輯上來講,這個集合應(yīng)當(dāng)是 Check 的輸出結(jié)果而不是輸入?yún)?shù),但因為這個方法是遞歸調(diào)用的,在這種情況下使用參數(shù)更為方便。調(diào)用方最初調(diào)用時需要提供一個空的集合。
這篇里已經(jīng)有一個繪制函數(shù) z=f(x,y) 的 SVG 圖形的實現(xiàn)了:
https://blog.51cto.com/steed/2356431
不過當(dāng)時的函數(shù) f 是在編譯的時候指定的。既然這里可以對字符串形式的表達(dá)式進(jìn)行解析、檢查和求值,那么就可以構(gòu)建一個 Web 應(yīng)用,在運行時從客戶端接收一個表達(dá)式,并繪制函數(shù)的曲面圖??梢允褂?vars 集合來檢查表達(dá)式是否是一個只有兩個變量x、y的函數(shù)(為了簡單起見,還提供了半徑r,所以實際上是3個變量)。使用 Check 方法來拒絕掉不規(guī)范的表達(dá)式,這樣就不會在下面函數(shù)的40000個計算過程中(100x100的格子,每一個有4個角)重復(fù)這些檢查。
表達(dá)式求值器已經(jīng)完成了,把它作為一個包引入。然后把繪制函數(shù)圖形加上 Web 應(yīng)用的代碼重新實現(xiàn)一遍,完整的代碼如下:
package main import ( "fmt" "io" "log" "math" "net/http" ) import "gopl/output/expression_evaluator/eval" const ( width, height = 600, 320 // canvas size in pixels cells = 100 // number of grid cells xyrange = 30.0 // x, y axis range (-xyrange..+xyrange) xyscale = width / 2 / xyrange // pixels per x or y unit zscale = height * 0.4 // pixels per z unit ) var sin30, cos30 = 0.5, math.Sqrt(3.0 / 4.0) // sin(30°), cos(30°) func corner(f func(x, y float64) float64, i, j int) (float64, float64) { // find point (x,y) at corner of cell (i,j) x := xyrange * (float64(i)/cells - 0.5) y := xyrange * (float64(j)/cells - 0.5) z := f(x, y) // compute surface height z // project (x,y,z) isometrically onto 2-D SVG canvas (sx,sy) sx := width/2 + (x-y)*cos30*xyscale sy := height/2 + (x+y)*sin30*xyscale - z*zscale return sx, sy } func surface(w io.Writer, f func(x, y float64) float64) { fmt.Fprintf(w, "<svg xmlns='http://www.w3.org/2000/svg' "+ "style='stroke: grey; fill: white; stroke-width: 0.7' "+ "width='%d' height='%d'>", width, height) for i := 0; i < cells; i++ { for j := 0; j < cells; j++ { ax, ay := corner(f, i+1, j) bx, by := corner(f, i, j) cx, cy := corner(f, i, j+1) dx, dy := corner(f, i+1, j+1) fmt.Fprintf(w, "<polygon points='%g,%g %g,%g %g,%g %g,%g'/>\n", ax, ay, bx, by, cx, cy, dx, dy) } } fmt.Fprintln(w, "</svg>") } // 組合了解析(Parse方法)和檢查(Check方法)步驟 func parseAndCheck(s string) (eval.Expr, error) { if s == "" { return nil, fmt.Errorf("empty expression") } expr, err := eval.Parse(s) if err != nil { return nil, err } vars := make(map[eval.Var]bool) if err := expr.Check(vars); err != nil { return nil, err } for v := range vars { if v != "x" && v != "y" && v != "r" { return nil, fmt.Errorf("undefined variable: %s", v) } } return expr, nil } // 解析并檢查Get請求的表達(dá)式,用它來創(chuàng)建一個有兩個變量的匿名函數(shù)。 // 這個匿名函數(shù)與曲面繪制程序中的f有同樣的簽名。 func plot(w http.ResponseWriter, r *http.Request) { r.ParseForm() expr, err := parseAndCheck(r.Form.Get("expr")) if err != nil { http.Error(w, "bad expr: "+err.Error(), http.StatusBadRequest) return } w.Header().Set("Content-Type", "image/svg+xml") surface(w, func(x, y float64) float64 { r := math.Hypot(x, y) // distance from (0,0) return expr.Eval(eval.Env{"x": x, "y": y, "r": r}) }) } func main() { fmt.Println("http://localhost:8000/plot?expr=sin(-x)*pow(1.5,-r)") fmt.Println("http://localhost:8000/plot?expr=pow(2,sin(y))*pow(2,sin(x))/12") fmt.Println("http://localhost:8000/plot?expr=sin(x*y/10)/10") http.HandleFunc("/plot", plot) log.Fatal(http.ListenAndServe("localhost:8000", nil)) }
關(guān)于Go語言中怎么實現(xiàn)一個表達(dá)式求值器問題的解答就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,如果你還有很多疑惑沒有解開,可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識。
網(wǎng)站題目:Go語言中怎么實現(xiàn)一個表達(dá)式求值器
當(dāng)前鏈接:http://jinyejixie.com/article46/pppghg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供做網(wǎng)站、品牌網(wǎng)站制作、網(wǎng)站設(shè)計、網(wǎng)站收錄、網(wǎng)站維護(hù)、小程序開發(fā)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)