[前端漫谈] 做一个四则计算器
0x000 概述
近期重新開始學(xué)習(xí)計算機基礎(chǔ)方面的東西，比如計算機組成原理、網(wǎng)絡(luò)原理、編譯原理之類的東西，目前正好在學(xué)習(xí)編譯原理，開始對這一塊的東西感興趣，但是理論的學(xué)習(xí)有點枯燥無味，決定換種方式，那就是先實踐、遇到問題嘗試解決，用實踐推動理論。原本打算寫個中文JS解析的，但是好像有點難，先就找個簡單的來做吧，那就是解析一下四則運算，就有了這個項目，聲明：這是一個很簡單的項目，這是一個很簡單的項目，這是一個很簡單的項目。其中用到的詞法分析、語法分析、自動機都是用簡單的方式實現(xiàn)，畢竟比較菜。
0x001 效果
-
源碼地址：github
-
實現(xiàn)功能：
- 任意順序的四則+-*/正整數(shù)運算
- 支持()
- 前端后端通用
- 提供直接計算函數(shù)
- 提供四則運算表達式轉(zhuǎn)逆波蘭AST函數(shù)
- 提供語法分析函數(shù)(暫時只支持上下兩個字符判定)
-
效果演示：
0x002 實現(xiàn)
既然說很簡單，那不管用到的理論和實現(xiàn)的方式都一定要都很簡單，實現(xiàn)這個效果一共需要克服三個問題：
0x003 解決問題1: 如何實現(xiàn)優(yōu)先級運算
1. 暫時忽略優(yōu)先級
如果沒有優(yōu)先級問題，那實現(xiàn)一個計算十分的簡單，比如下面的代碼可以實現(xiàn)一個簡單的加減或者乘除計算（10以內(nèi)，超過一位數(shù)會遇到問題2，這里先簡單一點，避過問題2）：
let calc = (input) => {let calMap = {'+': (num1, num2) => num1 + num2,'-': (num1, num2) => num1 - num2,'*': (num1, num2) => num1 * num2,'/': (num1, num2) => num1 / num2,}input = [...input].reverse()while (input.length >= 2) {let num1 = +input.pop()let op = input.pop()let num2 = +input.pop()input.push(calMap[op](num1, num2))}return input[0]}expect(calc('1+2+3+4+5-1')).toEqual(14)expect(calc('1*2*3/3')).toEqual(2) 復(fù)制代碼算法步驟:
- 將輸入打散成一個棧，因為是10以內(nèi)的，所以每個數(shù)只有一位：input = [...input].reverse() 復(fù)制代碼
- 每次取出三位，如果是正確的輸入，則取出的三位，第一位是數(shù)字，第二位是操作符，第三位是數(shù)字：let num1 = +input.pop() let op = input.pop() let num2 = +input.pop() 復(fù)制代碼
- 根據(jù)操作符做運算后將結(jié)果推回棧中，又形成了這么一個流程，一直到最后棧中只剩下一個數(shù)，或者說每次都要取出3個數(shù)，所以如果棧深度<=2，那就是最后的結(jié)果了：while (input.length >= 2) {// ......input.push(calMap[op](num1, num2)) } 復(fù)制代碼
動畫演示：
2. 考慮優(yōu)先級
但是現(xiàn)在需要考慮優(yōu)先級，比如*/的優(yōu)先級大于+-，()的運算符最高，那如何解決呢，其實都已經(jīng)有解決方案了，我用的是后綴表達式，也叫逆波蘭式
- 后綴表達式： 所謂的后綴表達式，就是將操作符放在表達式的最后邊，比如1+1表示成11+。
- 中綴表達式： 所謂的中綴表達式，其實就是我們平常使用的寫法了，這里不做深入。
- 前綴表達式 所謂的后綴表達式，就是將操作符放在表達式的最前邊，比如1+1表示成+11，這里不做深入
逆波蘭式可以參考下列文章
- Wiki-逆波蘭表示法
- 知乎-什么是逆波蘭表達式
3. 逆波蘭式解決優(yōu)先級問題
在逆波蘭式子中，1+1*2可以轉(zhuǎn)化為112*+ 代碼演示：
let calc = (input) => {let calMap = {'+': (num1, num2) => num1 + num2,'-': (num1, num2) => num1 - num2,'*': (num1, num2) => num1 * num2,'/': (num1, num2) => num1 / num2,}input = [...input].reverse()let resultStack = []while (input.length) {let token = input.pop()if (/[0-9]/.test(token)) {resultStack.push(token)continue}if (/[+\-*/]/.test(token)) {let num1 = +resultStack.pop()let num2 = +resultStack.pop()resultStack.push(calMap[token](num1, num2))continue}}return resultStack[0] } expect(calc('123*+')).toEqual(7) 復(fù)制代碼轉(zhuǎn)化之后計算步驟如下：
動畫演示：
轉(zhuǎn)化成逆波蘭式之后有兩個優(yōu)點：
- 不關(guān)心運算符優(yōu)先級
- 去除括號，比如(1+2)*(3+4)，可以轉(zhuǎn)化為12+34+*，按照逆波蘭式運算方法即可完成運算
4. 中綴轉(zhuǎn)后綴
這是問題1的最后一個小問題了，這個問題的實現(xiàn)過程如下：
let parse = (input) => {input = [...input].reverse()let resultStack = [], opStack = []while (input.length) {let token = input.pop()if (/[0-9]/.test(token)) {resultStack.push(token)continue}if (/[+\-*/]/.test(token)) {opStack.push(token)continue}}return [...resultStack, ...opStack.reverse()].join('')}expect(parse(`1+2-3+4-5`)).toEqual('12+3-4+5-') 復(fù)制代碼準備兩個棧，一個棧存放結(jié)果，一個棧存放操作符，最后將兩個棧拼接起來上面的實現(xiàn)可以將1+2-3+4-5轉(zhuǎn)化為12+3-4+5-，但是如果涉及到優(yōu)先級，就無能為力了，例如
expect(parse(`1+2*3`)).toEqual('123*+') 復(fù)制代碼1+2*3的轉(zhuǎn)化結(jié)果應(yīng)該是123*+，但其實轉(zhuǎn)化的結(jié)果卻是123+*，*/的優(yōu)先級高于+，所以，應(yīng)該做如下修改
let parse = (input) => {input = [...input].reverse()let resultStack = [], opStack = []while (input.length) {let token = input.pop()if (/[0-9]/.test(token)) {resultStack.push(token)continue} // if (/[+\-*/]/.test(token)) { // opStack.push(token) // continue // }if (/[*/]/.test(token)) {while (opStack.length) {let preOp = opStack.pop()if (/[+\-]/.test(preOp)) {opStack.push(preOp)opStack.push(token)token = nullbreak} else {resultStack.push(preOp)continue}}token && opStack.push(token)continue}if (/[+\-]/.test(token)) {while (opStack.length) {resultStack.push(opStack.pop())}opStack.push(token)continue}}return [...resultStack, ...opStack.reverse()].join('')}expect(parse(`1+2`)).toEqual('12+')expect(parse(`1+2*3`)).toEqual('123*+') 復(fù)制代碼到這里已經(jīng)解決了+-*/的優(yōu)先級問題，只剩下()的優(yōu)先級問題了，他的優(yōu)先級是最高的，所以這里做如下修改即可：
if (/[+\-]/.test(token)) {while (opStack.length) {let op=opStack.pop()if (/\(/.test(op)){opStack.push(op)break}resultStack.push(op)}opStack.push(token)continue } if (/\(/.test(token)) {opStack.push(token)continue } if (/\)/.test(token)) {let preOp = opStack.pop()while (preOp !== '('&&opStack.length) {resultStack.push(preOp)preOp = opStack.pop()}continue } 復(fù)制代碼動畫示例：
如此，就完成了中綴轉(zhuǎn)后綴了，那么整個問題1就已經(jīng)被解決了，通過calc(parse(input))就能完成中綴=>后綴=>計算的整個流程了。0x004 解決問題2:分割字符串
雖然上面已經(jīng)解決了中綴=>后綴=>計算的大問題，但是最基礎(chǔ)的問題還沒解決，那就是輸入問題，在上面問題1的解決過程中，輸入不過是簡單的切割，而且還局限在10以內(nèi)。而接下來，要解決的就是這個輸入的問題，如何分割輸入，達到要求？
- 解決方式1：正則，雖然正則可以做到如下，做個簡單的demo還是可以的，但是對于之后的語法檢測之類的東西不太有利，所以不太好，我放棄了這種方法(1+22)*(333+4444)`.match(/([0-9]+)|([+\-*/])|(\()|(\))/g) // 輸出 // (11)["(", "1", "+", "22", ")", "*", "(", "333", "+", "4444", ")"] 復(fù)制代碼
- 解決方法2：逐個字符分析，其大概的流程是while(input.length){let token = input.pop()if(/[0-9]/.test(token)) // 進入數(shù)字分析if(/[+\-*/\(\)]/.test(token))// 進入符號分析 } 復(fù)制代碼
接下來試用解決方案2來解決這個問題：
1 定義節(jié)點結(jié)構(gòu)
當我們分割的時候，并不單純保存值，而是將每個節(jié)點保存成一個相似的結(jié)構(gòu)，這個結(jié)構(gòu)可以使用對象表示：
{type:'',value:'' } 復(fù)制代碼其中，type是節(jié)點類型，可以將四則運算中所有可能出現(xiàn)的類型歸納出來，我的歸納如下：
TYPE_NUMBER: 'TYPE_NUMBER', // 數(shù)字TYPE_LEFT_BRACKET: 'TYPE_LEFT_BRACKET', // (TYPE_RIGHT_BRACKET: 'TYPE_RIGHT_BRACKET', // )TYPE_OPERATION_ADD: 'TYPE_OPERATION_ADD', // +TYPE_OPERATION_SUB: 'TYPE_OPERATION_SUB', // -TYPE_OPERATION_MUL: 'TYPE_OPERATION_MUL', // *TYPE_OPERATION_DIV: 'TYPE_OPERATION_DIV', // / 復(fù)制代碼value則是對應(yīng)的真實值，比如123、+、-、*、/。
2 數(shù)字處理
如果是數(shù)字，則繼續(xù)往下讀，直到不是數(shù)字為止，將這過程中所有的讀取結(jié)果放到value中，最后入隊。
if (token.match(/[0-9]/)) {let next = tokens.pop()while (next !== undefined) {if (!next.match(/[0-9]/)) breaktoken += nextnext = tokens.pop()}result.push({type: type.TYPE_NUMBER,value: +token})token = next } 復(fù)制代碼3 符號處理
先定義一個符號和類型對照表，如果不在表中，說明是異常輸入，拋出異常，如果取到了，說明是正常輸入，入隊即可。
const opMap = {'(': type.TYPE_LEFT_BRACKET,')': type.TYPE_RIGHT_BRACKET,'+': type.TYPE_OPERATION_ADD,'-': type.TYPE_OPERATION_SUB,'*': type.TYPE_OPERATION_MUL,'/': type.TYPE_OPERATION_DIV } let type = opMap[token] if (!type) throw `error input: ${token}` result.push({type,value: token, }) 復(fù)制代碼4 總結(jié)
這樣就完成了輸入的處理，這時候，其他的函數(shù)也需要處理一下，應(yīng)為輸入已經(jīng)從字符串變成了tokenize之后的序列了，修改完成之后就是可以calc(parse(tokenize()))完成一整套騷操作了。
0x005 解決問題3：語法檢測
語法檢測要解決的問題其實就是判斷輸入的正確性，是否滿足四則運算的規(guī)則，這里用了類似狀機的思想，不過簡單到爆炸，并且只能做單步判定～～ 定義一個語法表，該表定義了一個節(jié)點后面可以出現(xiàn)的節(jié)點類型，比如，+后面只能出現(xiàn)數(shù)字或者(之類。
let syntax = {[type.TYPE_NUMBER]: [type.TYPE_OPERATION_ADD,type.TYPE_OPERATION_SUB,type.TYPE_OPERATION_MUL,type.TYPE_OPERATION_DIV,type.TYPE_RIGHT_BRACKET],[type.TYPE_OPERATION_ADD]: [type.TYPE_NUMBER,type.TYPE_LEFT_BRACKET],//... } 復(fù)制代碼這樣我們就可以簡單的使用下面的語法判定方法了：
while (tokens.length) {// ...let next = tokens.pop()if (!syntax[token.type].includes(next.type)) throw `syntax error: ${token.value} -> ${next.value}`// ...} 復(fù)制代碼對于()，這里使用的是引用計數(shù)，如果是(，則計數(shù)+1，如果是)，則計數(shù)-1，檢測到最后的時候判定一下計數(shù)就好了：
// ...if (token.type === type.TYPE_LEFT_BRACKET) {bracketCount++}// ...if (next.type === type.TYPE_RIGHT_BRACKET) {bracketCount--}// ...if (bracketCount < 0) {throw `syntax error: toooooo much ) -> )`}// ... 復(fù)制代碼0x006 總結(jié)
- 該文章存在一些問題：
- 我推導(dǎo)不出為啥要用逆波蘭式，只是知道有這么一個解決方案，拿過來用而已，而不是由問題推導(dǎo)出解決方案。
- 文字功底不夠，講的不夠 cool。
- 該實現(xiàn)也存在一些問題：
- 并非完全用編譯原理的思想去實現(xiàn)，而是自己摸解決方案，先實踐，后了解問題。
- 并沒有參考太多別人的實現(xiàn)，有點閉門造車的感覺。
- 思考：
- 對于()的處理或許可以使用遞歸的方式，進入()之后重新開始一個新的表達式解析
- 思考不夠全，單元測試覆蓋不夠，許多坑還不知道在哪兒
總之：文章到此為止，有很多不夠詳細的地方還請見諒，多多交流，共同成長。
0x007 資源
- 編譯原理課程
- 源碼
- 動畫制作軟件Principle
轉(zhuǎn)載于:https://juejin.im/post/5c2c7ca56fb9a04a0d56f60b
總結(jié)
以上是生活随笔為你收集整理的[前端漫谈] 做一个四则计算器的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java虚拟机-第二篇-GC算法与内存分
- 下一篇： Git 2.19 对Diff、Branc