[前端漫談] 做一個四則計算器

馬永翠發布于2019-08-23 14:27 / 1364人閱讀

摘要：概述近期重新開始學習計算機基礎方面的東西，比如計算機組成原理網絡原理編譯原理之類的東西，目前正好在學習編譯原理，開始對這一塊的東西感興趣，但是理論的學習有點枯燥無味，決定換種方式，那就是先實踐遇到問題嘗試解決，用實踐推動理論。

0x000 概述

近期重新開始學習計算機基礎方面的東西，比如計算機組成原理、網絡原理、編譯原理之類的東西，目前正好在學習編譯原理，開始對這一塊的東西感興趣，但是理論的學習有點枯燥無味，決定換種方式，那就是先實踐、遇到問題嘗試解決，用實踐推動理論。原本打算寫個中文JS解析的，但是好像有點難，需要慢慢實現，于是就找個簡單的來做，那就是解析一下四則運算，就有了這個項目，聲明：這是一個很簡單的項目，這是一個很簡單的項目，這是一個很簡單的項目。其中用到的詞法分析、語法分析、自動機都是用簡單的方式實現，畢竟比較菜。

0x001 效果

源碼地址：github

實現功能：

任意順序的四則+-*/正整數運算

支持()

前端后端通用

提供直接計算函數

提供四則運算表達式轉逆波蘭AST函數

提供語法分析函數(暫時只支持上下兩個字符判定)

效果演示：

0x002 實現

既然說很簡單，那不管用到的理論和實現的方式都一定要都很簡單，實現這個效果一共需要克服三個問題：

如何實現優先級計算，比如*/()的優先級大于+-。

如何分割字符串，比如如何識別數字、符號和錯誤字符，也就是詞素化。

如何實現語法檢測，也就是讓表達式的規則滿足要求，比如+后面比如跟隨數字或者(（這里將-當作操作，而不是符號）。

0x003 解決問題1: 如何實現優先級運算 1. 暫時忽略優先級

如果沒有優先級問題，那實現一個計算十分的簡單，比如下面的代碼可以實現一個簡單的加減或者乘除計算（10以內，超過一位數會遇到問題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)

算法步驟:

將輸入打散成一個棧，因為是10以內的，所以每個數只有一位：

input = [...input].reverse()

每次取出三位，如果是正確的輸入，則取出的三位，第一位是數字，第二位是操作符，第三位是數字：

let num1 = +input.pop()
let op = input.pop()
let num2 = +input.pop()

根據操作符做運算后將結果推回棧中，又形成了這么一個流程，一直到最后棧中只剩下一個數，或者說每次都要取出3個數，所以如果棧深度<=2，那就是最后的結果了：

while (input.length >= 2) {
    // ......
    input.push(calMap[op](num1, num2))
}

動畫演示：

2. 考慮優先級

但是現在需要考慮優先級，比如*/的優先級大于+-，()的運算符最高，那如何解決呢，其實都已經有解決方案了，我用的是后綴表達式，也叫逆波蘭式

后綴表達式：
所謂的后綴表達式，就是將操作符放在表達式的最后邊，比如1+1表示成11+。

中綴表達式：
所謂的中綴表達式，其實就是我們平常使用的寫法了，這里不做深入。

前綴表達式
所謂的后綴表達式，就是將操作符放在表達式的最前邊，比如1+1表示成+11，這里不做深入

逆波蘭式可以參考下列文章

Wiki-逆波蘭表示法

知乎-什么是逆波蘭表達式

3. 逆波蘭式解決優先級問題

在逆波蘭式子中，1+1*2可以轉化為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)

轉化之后計算步驟如下：

初始化一個棧

    let resultStack = []

每次從表達式中取出一位

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
}

如果表達式不為空，進入步驟2，如果表達式空了，棧中的數就是最后的結果，計算完成

while (input.length) {
    // ...
}
return resultStack[0]

動畫演示：

轉化成逆波蘭式之后有兩個優點：

不關心運算符優先級

去除括號，比如(1+2)*(3+4)，可以轉化為12+34+*，按照逆波蘭式運算方法即可完成運算

4. 中綴轉后綴

這是問題1的最后一個小問題了，這個問題的實現過程如下：

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-")

準備兩個棧，一個棧存放結果，一個棧存放操作符，最后將兩個棧拼接起來上面的實現可以將1+2-3+4-5轉化為12+3-4+5-，但是如果涉及到優先級，就無能為力了，例如

        expect(parse(`1+2*3`)).toEqual("123*+")

1+2*3的轉化結果應該是123*+，但其實轉化的結果卻是123+*，*/的優先級高于+，所以，應該做如下修改

 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 = null
                            break
                        } 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*+")

當操作符為*/的時候，取出棧頂元素，判斷棧中的元素的優先級低是否低于*/，如果是就直接將操作符推入opStack，然后退出，否則一直將棧中取出的元素推入resultStack。

if (/[+-]/.test(preOp)) {
     opStack.push(preOp)// 這里用了棧來做判斷，所以判斷完還得還回去...
     opStack.push(token)
     token = null
     break
}else {
    resultStack.push(preOp)
    continue
}

還要注意棧空掉的情況，需要將操作符直接入棧。

    token && opStack.push(token)
    continue

當操作符為+-的時候，因為已經是最低的優先級了，所以直接將所有的操作符出棧就行了

if (/[+-]/.test(token)) {
    while (opStack.length) {
        resultStack.push(opStack.pop())
    }
    opStack.push(token)
    continue
}

到這里已經解決了+-*/的優先級問題，只剩下()的優先級問題了，他的優先級是最高的，所以這里做如下修改即可：

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
}

當操作符是+-的時候，不再無腦彈出，如果是(就不彈出了

while (opStack.length) {
        let op=opStack.pop()
        if (/(/.test(op)){
            opStack.push(op)
            break
        }
        resultStack.push(op)
    }
    opStack.push(token)

當操作符是(的時候，就推入opStack

if (/(/.test(token)) {
    opStack.push(token)
    continue
}

當操作符是)的時候，就持續彈出opStack到resultStack，直到遇到(，(不推入resultStack

if (/)/.test(token)) {
    let preOp = opStack.pop()
    while (preOp !== "("&&opStack.length) {
        resultStack.push(preOp)
        preOp = opStack.pop()
    }
    continue
}

完整代碼：

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)) {
           while (opStack.length) {
               let preOp = opStack.pop()
               if (/[+-]/.test(preOp)) {
                   opStack.push(preOp)
                   opStack.push(token)
                   token = null
                   break
               } else {
                   resultStack.push(preOp)
                   continue
               }
           }
           token && opStack.push(token)
           continue
       }
       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
       }
   }
   return [...resultStack, ...opStack.reverse()].join("")

動畫示例：

如此，就完成了中綴轉后綴了，那么整個問題1就已經被解決了，通過calc(parse(input))就能完成中綴=>后綴=>計算的整個流程了。

0x004 解決問題2:分割字符串

雖然上面已經解決了中綴=>后綴=>計算的大問題，但是最基礎的問題還沒解決，那就是輸入問題，在上面問題1的解決過程中，輸入不過是簡單的切割，而且還局限在10以內。而接下來，要解決的就是這個輸入的問題，如何分割輸入，達到要求？

解決方式1：正則，雖然正則可以做到如下，做個簡單的demo還是可以的，但是對于之后的語法檢測之類的東西不太有利，所以不太好，我放棄了這種方法

(1+22)*(333+4444)`.match(/([0-9]+)|([+-*/])|(()|())/g)
// 輸出
// (11)?["(", "1", "+", "22", ")", "*", "(", "333", "+", "4444", ")"]

解決方法2：逐個字符分析，其大概的流程是

while(input.length){
    let token = input.pop()
    if(/[0-9]/.test(token)) // 進入數字分析
    if(/[+-*/()]/.test(token))// 進入符號分析
}

接下來試用解決方案2來解決這個問題：

1 定義節點結構

當我們分割的時候，并不單純保存值，而是將每個節點保存成一個相似的結構，這個結構可以使用對象表示：

{
    type:"",
    value:""
}

其中，type是節點類型，可以將四則運算中所有可能出現的類型歸納出來，我的歸納如下：

    TYPE_NUMBER: "TYPE_NUMBER", // 數字
    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", // /

value則是對應的真實值，比如123、+、-、*、/。

2 數字處理

如果是數字，則繼續往下讀，直到不是數字為止，將這過程中所有的讀取結果放到value中，最后入隊。

if (token.match(/[0-9]/)) {
    let next = tokens.pop()
    while (next !== undefined) {
        if (!next.match(/[0-9]/)) break
        token += next
        next = tokens.pop()
    }
    result.push({
        type: type.TYPE_NUMBER,
        value: +token
    })
    token = next
}

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,
})

4 總結

這樣就完成了輸入的處理，這時候，其他的函數也需要處理一下，應為輸入已經從字符串變成了tokenize之后的序列了，修改完成之后就是可以calc(parse(tokenize()))完成一整套騷操作了。

0x005 解決問題3：語法檢測

語法檢測要解決的問題其實就是判斷輸入的正確性，是否滿足四則運算的規則，這里用了類似狀機的思想，不過簡單到爆炸，并且只能做單步判定～～
定義一個語法表，該表定義了一個節點后面可以出現的節點類型，比如，+后面只能出現數字或者(之類。

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
    ],
    [type.TYPE_OPERATION_SUB]: [
        type.TYPE_NUMBER,
        type.TYPE_LEFT_BRACKET
    ],
    [type.TYPE_OPERATION_MUL]: [
        type.TYPE_NUMBER,
        type.TYPE_LEFT_BRACKET
    ],
    [type.TYPE_OPERATION_DIV]: [
        type.TYPE_NUMBER,
        type.TYPE_LEFT_BRACKET
    ],
    [type.TYPE_LEFT_BRACKET]: [
        type.TYPE_NUMBER,
        type.TYPE_LEFT_BRACKET
    ],
    [type.TYPE_RIGHT_BRACKET]: [
        type.TYPE_OPERATION_ADD,
        type.TYPE_OPERATION_SUB,
        type.TYPE_OPERATION_MUL,
        type.TYPE_OPERATION_DIV,
        type.TYPE_RIGHT_BRACKET
    ]
}

這樣我們就可以簡單的使用下面的語法判定方法了：

 while (tokens.length) {
    // ...
    let next = tokens.pop()
    if (!syntax[token.type].includes(next.type)) throw `syntax error: ${token.value} -> ${next.value}`
    // ...
 }

對于()，這里使用的是引用計數，如果是(，則計數+1，如果是)，則計數-1，檢測到最后的時候判定一下計數就好了：

    // ...
    if (token.type === type.TYPE_LEFT_BRACKET) {
        bracketCount++
    }
    // ...
    if (next.type === type.TYPE_RIGHT_BRACKET) {
        bracketCount--
    }
    // ...
    if (bracketCount < 0) {
        throw `syntax error: toooooo much ) -> )`
    }
    // ...

0x006 總結

該文章存在一些問題：

我推導不出為啥要用逆波蘭式，只是知道有這么一個解決方案，拿過來用而已，而不是由問題推導出解決方案。

文字功底不夠，講的不夠 cool。

該實現也存在一些問題：

并非完全用編譯原理的思想去實現，而是自己摸解決方案，先實踐，后了解問題。

并沒有參考太多別人的實現，有點閉門造車的感覺。

思考：

對于()的處理或許可以使用遞歸的方式，進入()之后重新開始一個新的表達式解析

思考不夠全，單元測試覆蓋不夠，許多坑還不知道在哪兒

總之：文章到此為止，有很多不夠詳細的地方還請見諒，多多交流，共同成長。

0x007 資源

編譯原理課程

源碼

動畫制作軟件Principle

云服務器 GPU云服務器四則運算計算器 js 做一個做一個網站如何做一個

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/100634.html

編譯原理實戰入門：用 JavaScript 寫一個簡單的四則運算編譯器（四）結語

摘要：四則運算編譯器，雖然說功能很簡單，只能編譯四則運算表達式。再復雜的編譯器再簡單的編譯器，功能上是差不多的，只是復雜的編譯器實現上會更困難。每一章都是理論與實踐結合的經典，從計算機硬件知識到軟件體系，再到編譯原理和操作系統。四則運算編譯器，雖然說功能很簡單，只能編譯四則運算表達式。但是編譯原理前端部分幾乎都有涉及，詞法分析，語法分析，還有代碼生成。再復雜的編譯器、再簡單的編譯器，功能...

chemzqm 2019-08-23 18:24 評論0 收藏0
[前端漫談_3] 從 filter 聊到 Promise

摘要：前言在學習前端的時候，我總是能聽到很多高級詞匯，比如今天會聊到的函數式編程高階函數。接下來我們看看，高階函數有可能會遇到的問題，又如何去解決。前言在學習前端的時候，我總是能聽到很多高級詞匯，比如今天會聊到的函數式編程(Functional Programming) & 高階函數 (Higher-order function) 。但是當你真正的理解什么是函數式編程 & 高階函數 ...

crossoverJie 2019-08-23 17:56 評論0 收藏0
漫談前端性能突破 React 應用瓶頸

摘要：表示調用棧在下一將要執行的任務。兩方性能解藥我們一般有兩種方案突破上文提到的瓶頸將耗時高成本高易阻塞的長任務切片，分成子任務，并異步執行這樣一來，這些子任務會在不同的周期執行，進而主線程就可以在子任務間隙當中執行更新操作。 showImg(https://segmentfault.com/img/remote/1460000016008111); 性能一直以來是前端開發中非常重要的話題...

whlong 2019-08-26 12:10 評論0 收藏0