[數據結構]表達式樹——手動eval()

02-19

0x00 Prologue

過春節啦！祝大家新年快樂哇~有一段時間沒有寫文章了，前幾天正好把寒假的作業寫了一些，今天更一篇依舊是介紹樹形數據結構的文章吧....這次看一個沒有Zkw線段樹那麼複雜的數據結構——表達式樹(Expression Tree)。

本篇文章將對：

表達式樹的工作原理
表達式樹建立步驟
表達式樹求值

進行介紹。文章代碼使用JavaScript(最近某個項目需要學習，正好用一用:P)，但是這個語言吧語法還是非常簡單易懂的...並且我會在需要解釋的地方打上注釋:D。

另外，文章會涉及一點非常簡單的詞法分析器的介紹。

0x01 表達式樹能幹啥？長啥樣？

Q: 給定一個合法的表達式字元串"(1+2)*(5-3)"，計算表達式的值。

<del>A: eval()！！(拉出去打死</del>

如果使用一些沒有eval()的語言怎麼搞？用表達式樹！

<del>建一下，玩一年，只要998，年底清倉大甩賣，表達式樹帶回家</del>

表達式樹就是將一個表達式解析成一棵滿二叉樹(如果所有合法操作符都是進行二元計算)，且所有非葉結點都是符號結點(+-*/)，葉子結點都是數字結點。對於(1+2)*(5-3)我們就可以構造出一棵這樣的表達式樹：

(1+2)*(5-3)的表達式樹

可以看出來，對表達式樹進行後序遍歷的結果就是原表達式的逆波蘭式(後綴表達式)。對表達式樹進行前序遍歷進行計算的結果就是我們表達式計算的結果。

0x02 從字元串建立表達式樹

0. 規定表達式組成成分

這裡為了簡化理解，就不介紹產生式了...這一部分就是規定什麼能出現在將被evaluate的字元串中，定義符號集以及對應的Token。這裡我們的計算器支持基礎四則運算，取模以及位運算(and, or, xor, shl, shr)，這些符號的token我們定義為OPERATOR；除了符號還有參與運算的數字，我們將數字分為兩種：INTEGER和DOUBLE。那麼我們就可以定義一個這樣的類：

const TokenType = { OPERATOR: OPERATOR, INT: INTEGER, DOUBLE: DECIMAL,}// 這裡是可以作為關鍵字開頭的符號表// 這樣做為了方便之後判斷Token...如果有更好的實現方法// 求大佬們賜教const operator_list = { +: 0, -: 0, *: 0, /: 0, %: 0, &: 0, |: 0, ^: 0, **: 0, <: 0, >: 0, ~: 0, (: 0, ): 0}class Token{ constructor(value, tag){ this.value = value; // 對應值 this.tag = tag; // Token類型(TokenType) }}

詞法分析

為了方便建樹時識別每個符號的含義，我們首先對表達式字元串進行詞法分析。這個過程會將字元串中的元素拆分成一個一個的Token。例如+是一個運算符，我們可以定義為OPERATOR。我們將編寫一個簡單的詞法分析器(Lexer)對表達式字元串進行詞法分析。

Lexer的作用

(上圖是對表達式(1+2)*3.5進行詞法分析後的結果。 )

實現一個Lexer並不難，我們只需要將字元串從左向右掃一遍，將不同類別的詞素分離開即可。例如：當前位置的符號是>，那麼我們可以猜測這有可能是shr符號；這時向後看一位，如果是>那麼就可以確定這是要shr了。

為了方便我們實現這個Lexer，首先我們寫一個Reader類，用於逐位讀取一個可以用下標操作符的對象（用於讀取輸入的表達式和之後的Token列表）：

class Reader{ // Reader 職階 constructor(input_data){ this.seq = input_data; this.cursor = 0; this.urng = input_data.length; } next() { return this.seq[this.cursor++]; // 返回當前位置的字元並將游標向後移動1 } cursor_data() { return this.seq[this.cursor] // 返回當前游標所指的數據 } has_next() { return this.cursor < this.urng; // 調用next()是否還有數據 } peek() { return this.seq[this.cursor + 1]; // 向後看一位 }}

寫好Reader類之後，我們再實現Lexer：

var reader;class Lexer{ // Lexer 職階 constructor(input_expreesion){ reader = new Reader(input_expreesion); } parse(){ var token_list = []; // 保存解析出的Token，Token列表 let last_token = () => {return token_list[token_list.length - 1]}; // 返回上一個解析的Token let is_digit = (x) => {return x >= 0 && x <= 9}; let is_escape = (x) => {return x === || x === || x === }; function readNum() { var ans = { v: , t: TokenType.INT }; // 讀取剩餘的數字或小數點 while(reader.has_next() && (is_digit(reader.cursor_data()) || reader.cursor_data() === . || is_escape(reader.cursor_data()))){ if(is_escape(reader.cursor_data())) { // 感謝@被子飛了提醒...這裡需要把cursor向後移動一位 reader.next(); continue; }; ans.v += reader.next(); } if (reader.has_next() && reader.cursor_data() === e && (reader.peek() === - || reader.peek() === +)){ ans.v += reader.next() + reader.next(); while(reader.has_next() && is_digit(reader.cursor_data())){ ans.v += reader.next(); } } // 科學計數 if(ans.v.search(.) !== -1 || ans.v.search(e-) !== -1){ ans.t = TokenType.DOUBLE; } return ans; } while (reader.has_next()){ var cur = reader.next(); if(is_escape(cur)) continue; if(is_digit(cur)) { var ret = readNum(); token_list.push(new Token(cur + ret.v, ret.t)); }else if(cur in operator_list){ var prev = last_token(); if(typeof prev !== undefined) prev = prev.tag; if(cur === -){ // 分兩種情況，1. 負數 2. 減法 if (typeof prev !== undefined && (prev === TokenType.INT || prev === TokenType.DOUBLE)){ token_list.push(new Token(cur, TokenType.OPERATOR)); // 作為運算符處理 }else{ var ret = readNum(); cur += ret.v; token_list.push(new Token(cur, ret.t)); } }else if(cur === ~){ var ret = readNum(); token_list.push(new Token(cur + ret.v, TokenType.INT)); }else if((cur === * || cur === < || cur === >) && reader.has_next() && reader.cursor_data() === cur){ cur += reader.next() // 當前位置和上一個位置是同一個Operator，兩個組合成指定Operator(** << >>) token_list.push(new Token(cur, TokenType.OPERATOR)); }else{ token_list.push(new Token(cur, TokenType.OPERATOR)); } }else{ throw "Error character @ " + (reader.cursor - 1) + " " + cur; } } return token_list; }}

至此，一個簡單的Lexer就編寫完畢了。可以通過console.log(new Lexer("(1+2)*3"))看看解析是否正確。

e.g: (1.25+3e-2+1e+3)*5

Tokenize: (1.25+3e-2+1e+3)*5

0x03 通過Token列表建立表達式樹 & 求值

這時我們的Reader又派上用場了<del>(上吧！Reader，ATK +450↑)</del>。我們建立表達式樹的時候也需要從左向右掃一遍我們的Token們。我們需要兩個棧(Stack)存儲兩類數據：

Number Stack (數字棧)
Operator Stack (符號棧)

事實上，這裡的數字棧並不只存數字，而是存可被求值的結點。

為了方便之後的求值，我們定義兩種表達式樹節點：

常數結點
操作符結點

其中常數結點存儲一個單獨的值value和一個求值方法eval()（直接返回value）；操作符結點分為op，fi，和se，分別是操作符，左表達式，右表達式。注意左右表達式既可以是操作符結點也可以是常數結點。操作符結點也有一個求值方法eval()，判斷op並返回相應值：

常數結點：

class ConstNode{ constructor(v){ this.value = v; } eval(){ return this.value; }}

操作符結點：

class OperatorNode{ constructor(op, fi, se){ this.op = op; this.fi = fi; this.se = se; } eval(){ switch(this.op){ case +: return this.fi.eval() + this.se.eval(); case -: return this.fi.eval() - this.se.eval(); case *: return this.fi.eval() * this.se.eval(); case /: return this.fi.eval() / this.se.eval(); case %: return this.fi.eval() % this.se.eval(); case **: return this.fi.eval() ** this.se.eval(); case <<: return this.fi.eval() << this.se.eval(); case >>: return this.fi.eval() >> this.se.eval(); case &: return this.fi.eval() & this.se.eval(); case |: return this.fi.eval() | this.se.eval(); case ^: return this.fi.eval() ^ this.se.eval(); default: break; } }}

(Tips: 這裡使兩種結點求值方法名相同就是為了方便整棵樹的求值)

我們定義一個addNode()函數，這個函數會從數字棧中取出棧頂的兩個元素，然後再從符號棧中取出棧頂符號，最後將剛剛取出的符號和兩個表達式元素放入一個符號結點，加入到數字棧當中作為一個新的「數字」(可被求值對象)。

當從左向右掃描的時候如果遇到的Token是INTEGER或者DOUBLE，我們就直接將其處理一下（parseInt()或parseFloat()）放入數字棧中；如果遇到的是OPERATOR，我們按照運算優先順序進行操作。這裡不需要明確寫出運算優先順序，我們只需要一直執行addNode()直到遇到了比當前運算符優先順序低的符號為止(比如遇到了*和/，那麼我們就一直執行addNode()直到遇到+, -, &, |, ^)，最後再把當前運算符放入符號棧。

class ExpressionTreeConstructor{ constructor(tokenList){ reader = new Reader(tokenList); this.operator = []; // 符號棧 this.num = []; // 數字棧 } addNode(){ var se = this.num.pop(); // LIFO, 第二個在前面 var fi = new ConstNode(0); if(this.num.length !== 0){ fi = this.num.pop(); } var op = this.operator.pop(); // 取出棧頂符號 this.num.push(new OperatorNode(op, fi, se)); // 將三個元素打包成符號結點放入數字棧中 } get opTop(){ return this.operator[this.operator.length - 1] } build_tree(){ while(reader.has_next()){ var cur = reader.next(); console.log(this.num, cur.value); switch (cur.tag) { case TokenType.INT: if (cur.value.startsWith(~)) { this.num.push(new ConstNode(~parseInt(cur.value.slice(1)))); } else { this.num.push(new ConstNode(parseInt(cur.value))); } break; case TokenType.DOUBLE: if (cur.value.startsWith(~)) { // 這個應該沒啥意義... this.num.push(new ConstNode(~parseFloat(cur.value.slice(1)))); } else { this.num.push(new ConstNode(parseFloat(cur.value))); } break; case TokenType.OPERATOR: switch(cur.value){ case (: this.operator.push((); // 這個符號優先順序最低，直接加入符號棧 break; case ): while(this.operator.length && this.opTop !== (){ // 將括弧之間的全都處理一遍 this.addNode(); } this.operator.pop(); // 彈掉棧頂的( break; case %: case **: while (this.operator.length && this.opTop === cur.value) { // 取模與exponential比其他運算符優先順序高，所以遇到這兩個符號時只能處理剩餘的取模和exp this.addNode(); } this.operator.push(cur.value); // 將當前符號加入符號棧 break; case *: case /: while (this.operator.length && (this.opTop === * || this.opTop === /)) { this.addNode(); // 乘除 } this.operator.push(cur.value); break; case +: case -: while (this.operator.length && this.opTop !== ( && this.opTop !== | && this.opTop !== & && this.opTop !== ^) { // 處理到這些符號就停止，位運算符號優先順序低，不能同時加入樹中 this.addNode(); } this.operator.push(cur.value); break; case |: case &: case ^: case <<: case >>: while(this.operator.length && this.opTop !== (){ this.addNode(); } this.operator.push(cur.value); break; default: throw "Error Operator " + cur.value; } default: break; } } while(this.operator.length){ this.addNode(); // 用剩餘的結點把數字棧里解析好的結點組合起來 } return this.num[0]; // 最後返回根結點 }}

我們可以來看一下(1.25+3e-2+1e+3)*5的建樹結果：

對(1.25+3e-2+1e+3)*5建立表達式樹

求值就非常簡單了，我們已經定義了eval()函數，只需要再調用一下就行。

至此我們的表達式樹從簡單的詞法分析到建立就全部完成了。完整代碼如下：

0x04 Epilogue

表達式樹是一個不太被常用，但是實現起來並不困難的樹形結構 ... 做一個計算器可以用到它。比如前段時間打發時間寫的用於長度單位換算的小REPL:

AD1024/UnitEquationgithub.com

當然，如果你想做一個編程語言...emmmm 有點困難，因為AST比這個要複雜很多，而且計算表達式比較simple，不需要複雜的parser，但是編程語言嘛...parser複雜很多。這裡有個計算器的小REPL(應該還有bug)，就是嘗試不使用parser搞一個簡單的編程語言：

AD1024/Calculatorgithub.com

最後祝大家新年快樂，狗年大吉，萬事如意~