JavaScript 解析數(shù)學(xué)表達(dá)式的過程詳解
概要
本文以一個(gè) ?? 的解題思路，來分享如何解決問題。
解決的過程，可以作為解決工作中一般問題的通用思路。
希望同學(xué)有所收獲。
問題
通過JS解析數(shù)學(xué)表達(dá)式字符串。
(1 + (2 - (3 * 4 / 5 + 6 - (7 + 8))) + (9 - 10) * 11 + 12) + 13
表達(dá)式中包含基本的數(shù)學(xué)運(yùn)算符號+ 、 - 、 * 、 /和()小括號，數(shù)字都是正整數(shù)。
下面記錄了個(gè)人的思考過程。
拆解問題
正常在做數(shù)學(xué)運(yùn)算的時(shí)候，一般都是先進(jìn)行左側(cè)的運(yùn)算，拿左邊的運(yùn)算結(jié)果繼續(xù)和右邊的繼續(xù)運(yùn)算。從左到右運(yùn)算時(shí)，可能會遇到不同的操作符。
如果遇到
+、-，直接對運(yùn)算符左右兩側(cè)數(shù)字進(jìn)行加減運(yùn)算，拿到結(jié)果后和下一個(gè)繼續(xù)運(yùn)算。如果遇到了
*、/，則優(yōu)先計(jì)算乘除，在進(jìn)行加減運(yùn)算。如果遇到了
()，則小括號內(nèi)的表達(dá)式被視為一個(gè)整體參與運(yùn)算，在得到運(yùn)算結(jié)果后再參與小括號外的運(yùn)算。
以上是對一個(gè)程序問題場景的拆分，我們可以得到下面幾個(gè)原則
- 運(yùn)算是從左到右。
- 表達(dá)式中
+、-，直接拆分成左右兩個(gè) - 表達(dá)式中
*、/，則*、/可以被視為一個(gè)整體做優(yōu)先計(jì)算。如都是*、/同上。 - 表達(dá)式中
()，被視為一個(gè)整體
JS解析數(shù)學(xué)表達(dá)式，被拆解為上面的四個(gè)原則，即是我們需要解決的問題。所以在遇到一個(gè)大的問題時(shí)，我們第一步應(yīng)該是對問題進(jìn)行拆解。
在對一個(gè)個(gè)小問題進(jìn)行解答的時(shí)候，我們就把一個(gè)大的問題解決了。
下面逐一解決這四個(gè)問題。
解決問題
從左到右計(jì)算
從左到右計(jì)算，有兩個(gè)關(guān)鍵點(diǎn)從左到右和計(jì)算。
計(jì)算
我們先分析計(jì)算，在進(jìn)行+ - * /計(jì)算時(shí)，即利用運(yùn)算符號對兩側(cè)數(shù)字進(jìn)行運(yùn)算。下面用一個(gè)圖表示下1+2
這樣就確定了一個(gè)運(yùn)算操作的基本數(shù)據(jù)結(jié)構(gòu)，即二叉??。中間節(jié)點(diǎn)存儲運(yùn)算符號，left節(jié)點(diǎn)儲存左側(cè)的數(shù)值，right節(jié)點(diǎn)存儲右邊的數(shù)值。
從左到右
這里舉一個(gè)簡單的加法運(yùn)算表達(dá)式1 + 2 + 3 + 4來分析從左到右。我們從左到右遍歷這個(gè)這個(gè)表達(dá)式，可以得到下圖二叉??。
但是遍歷這樣的數(shù)據(jù)結(jié)構(gòu)得到的運(yùn)算過程是從右到左（深度遍歷先計(jì)算 3 + 4 一直到 1）。所以我們嘗試從右到左遍歷這個(gè)表達(dá)式，可以得到下圖。
現(xiàn)在我們就明確了編碼需要做的具體事項(xiàng)，即從右到左遍歷表達(dá)式，形成一個(gè)二叉??。基本的代碼如下：
const expression = 'xxxx';
const parse = (expression, l = 0, r = expression.length - 1) => {
for (let i = r; i >= l; i--) {
const v = expression[i];
let isNumber = true;
if (i === l) {
if (isNumber) {
return {
type: 'number',
value: Number(expression.slice(l, r + 1).trim()),
};
}
}
if (/[0-9]/.test(v) || v === ' ') {
continue;
}
isNumber = false;
return {
type: v,
left: parse(expression, l, i - 1),
right: parse(expression, i + 1, r),
}
}
}+ -拆分左右
對+ -進(jìn)行左右拆分，這個(gè)可以基于上面的代碼，稍調(diào)整下邏輯即可：
...
return {
type: v,
left: parse(expression, l, i - 1),
right: parse(expression, i + 1, r),
}
...更改為
...
if (v === '+' || v === '-') {
return {
type: v,
left: parse(expression, l, i - 1),
right: parse(expression, i + 1, r),
}
}
...* /拆分左右
相較于+ - 拆分左右，* /更加復(fù)雜些。我們應(yīng)該先拆分場景。
可以整理出兩個(gè)場景，僅包含* /和混合運(yùn)算。
1 + 2 * 3 / 41 * 2 * 3 / 4
我們在從右到左遍歷表達(dá)式時(shí)，我們在遇到* /，需要繼續(xù)向左遍歷，判斷表達(dá)式左邊是否有+ - 。
如果遇到了+ -，則按照 + -拆分左右 的原則解析。
如果是僅包含 * /，則我們需要拿遇到的第一個(gè)運(yùn)算符/，拆分左右。
我們調(diào)整下parse的邏輯
...
let firstTimeOrDivideOperator = null; // 記錄遇到的第一個(gè) * / 運(yùn)算符
let firstTimeOrDivideOperatorIdx = null; // 記錄遇到的第一個(gè) * / 運(yùn)算符的位置
...
// 遍歷到最左側(cè)，判斷 * / 左邊是否有 + -
if (i === l) {
...
// * / 拆分，需要遍歷到最左側(cè)，所里拆分邏輯寫這里
return {
type: firstTimeOrDivideOperator,
left: parse(expression, i, firstTimeOrDivideOperatorIdx - 1),
right: parse(expression, firstTimeOrDivideOperatorIdx + 1, r),
}
}
...
if ((v === '*' || v === '/') && !firstTimeOrDivideOperator) {
firstTimeOrDivideOperator = v
firstTimeOrDivideOperatorIdx = i
}()整體
()被視為一個(gè)整體，首先我們要知道哪兩個(gè)括號是一對。一個(gè)表達(dá)式如果剔除了+ - * /后，剩下的部分可能是這個(gè)樣子(()(()))。
我們從右到左分析這個(gè)字符串，在整個(gè)字符串中，遇到的第一個(gè)(，右側(cè)離它最近的那個(gè))，它們倆就是一對。然后我們將這一對()剔除。重復(fù)上面的操作即：
(()(()))(()(--))(()----)(------)--------
分析上面的步驟，我們可以知道，如果遇到)我們記錄下來，如果遇到(，則將將最近的)剔除。對數(shù)據(jù)結(jié)構(gòu)敏感的同學(xué)，一定會想到棧。
同時(shí)我們要記錄下(、)位置信息。
我們調(diào)整下parse的邏輯
const stock = []; // 先進(jìn)后出，每一次出棧，即一對 ()
const parenthesesPairPosition = {}
...
let parenthesesDep = 0; // 記錄小括號深度
...
if (v === ')') {
stock.push(i)
parenthesesDep++
} else if (v === '(') {
const last = stock.pop()
parenthesesPairPosition[i] = last
parenthesesDep--
}
if (i === l) {
...
if (parenthesesPairPosition[i] === r) {
return parse(expression, l + 1, r - 1)
}
...
}
...優(yōu)化
優(yōu)化一般是減少重復(fù)的工作。
我們可以快速定位上面解決問題內(nèi)容的 * / 拆分左右 部分有重復(fù)的工作。
1 + 2 * 3 / 4 在從右向左搜索字符串串時(shí)，第一遍我們就知道了連續(xù)的* /，第二遍我可以不用遍歷到最左側(cè)，按照搜索到的第一個(gè)* /拆分左右即可。
優(yōu)化上面的代碼：
const parse = (expression, l = 0, r = expression.length - 1, skipSearchTimeOrDivide = false) => {
...
let firstTimeOrDivideOperator = null; // 記錄遇到的第一個(gè) * / 運(yùn)算符
let firstTimeOrDivideOperatorIdx = null; // 記錄遇到的第一個(gè) * / 運(yùn)算符的位置
for (let i = r; i >= l; i--) {
...
// skipSearchTimeOrDivide 為 true 表示表達(dá)式是連續(xù)的 * /
if (skipSearchTimeOrDivide && firstTimeOrDivideOperator) {
return {
type: firstTimeOrDivideOperator,
left: parse(expression, l, firstTimeOrDivideOperatorIdx - 1, true),
right: parse(expression, firstTimeOrDivideOperatorIdx + 1, r),
}
}
if (i === l) {
...
return {
type: firstTimeOrDivideOperator,
left: parse(expression, l, firstTimeOrDivideOperatorIdx - 1, true),
right: parse(expression, firstTimeOrDivideOperatorIdx + 1, r),
}
}
...
if ((v === '*' || v === '/') && !firstTimeOrDivideOperator) {
firstTimeOrDivideOperator = v
firstTimeOrDivideOperatorIdx = i
}
}
}完整代碼
補(bǔ)充了剔除兩側(cè)空格和小括號、運(yùn)算和細(xì)節(jié)。
const stock = []; // 先進(jìn)后出，每一次出棧，即一對 ()
const parenthesesPairPosition = {}
// 剔除兩側(cè)空格
const removeBlank = (expression, l, r) => {
while (expression[l] === ' ') {
l++
}
while (expression[r] === ' ') {
r--
}
return [l, r]
}
// 剔除兩側(cè)小括號
const removeParentheses = (l, r) => {
if (parenthesesPairPosition[l] === r) return [++l, --r]
return [l, r]
}
const parse = (expression, l = 0, r = expression.length - 1, skipSearchTimeOrDivide = false) => {
let isNumber = true;
let parenthesesDep = 0; // 記錄小括號深度
let firstTimeOrDivideOperator = null; // 記錄遇到的第一個(gè) * / 運(yùn)算符
let firstTimeOrDivideOperatorIdx = null; // 記錄遇到的第一個(gè) * / 運(yùn)算符的位置
[l, r] = removeBlank(expression, l, r);
[l, r] = removeParentheses(l, r);
for (let i = r; i >= l; i--) {
const v = expression[i];
if (v === ')') {
stock.push(i)
parenthesesDep++
} else if (v === '(') {
const last = stock.pop()
parenthesesPairPosition[i] = last
parenthesesDep--
}
// skipSearchTimeOrDivide 為 true 表示表達(dá)式是連續(xù)的 * /
if (skipSearchTimeOrDivide && firstTimeOrDivideOperator) {
return {
type: firstTimeOrDivideOperator,
left: parse(expression, l, firstTimeOrDivideOperatorIdx - 1, true),
right: parse(expression, firstTimeOrDivideOperatorIdx + 1, r),
}
}
if (i === l) {
if (isNumber) {
return {
type: 'number',
value: Number(expression.slice(l, r + 1).trim()),
};
}
if (parenthesesPairPosition[i] === r) {
return parse(expression, l + 1, r - 1)
}
// * / 拆分，需要遍歷到最左側(cè)，所里拆分邏輯寫這里
return {
type: firstTimeOrDivideOperator,
left: parse(expression, l, firstTimeOrDivideOperatorIdx - 1, true),
right: parse(expression, firstTimeOrDivideOperatorIdx + 1, r),
}
}
if (/[0-9]/.test(v) || v === ' ') {
continue;
}
isNumber = false;
// parenthesesDep === 0 進(jìn)行表達(dá)式分析的時(shí)候要確保是同一層級
if (parenthesesDep === 0 && (v === '+' || v === '-')) {
return {
type: v,
left: parse(expression, l, i - 1),
right: parse(expression, i + 1, r),
}
}
if (parenthesesDep === 0 && (v === '*' || v === '/') && !firstTimeOrDivideOperator) {
firstTimeOrDivideOperator = v
firstTimeOrDivideOperatorIdx = i
}
}
}
const exec = ast => {
const recursion = ast => {
if (ast.type === '+') {
return recursion(ast.left) + recursion(ast.right)
} else if (ast.type === '-') {
return recursion(ast.left) - recursion(ast.right)
} else if (ast.type === '*') {
return recursion(ast.left) * recursion(ast.right)
} else if (ast.type === '/') {
return recursion(ast.left) / recursion(ast.right)
} else if (ast.type === 'number') {
return ast.value
}
}
return recursion(ast)
}
const expression = '(1 + (2 - (3 * 4 / 5 + 6 - (7 + 8))) + (9 - 10) * 11 + 12) + 13'
console.log(exec(parse(expression)) === eval(expression))總結(jié)
解決一般問題的通用思路：
- 拆分問題
- 基于問題拆分場景，根據(jù)不同的情況編寫邏輯
- 優(yōu)化代碼，分析代碼中重復(fù)的工作等等
同時(shí)我們也要拓展編程相關(guān)基本知識，不斷學(xué)習(xí)。這樣在面對問題時(shí)，可以快速想到可能的解決方案。 例如上面的問題，同學(xué)對數(shù)據(jù)結(jié)構(gòu)有所了解的話，則分析小括號可以迅速想到用棧去解決。另外一點(diǎn)就是編譯原理中也有講到掃描運(yùn)算表達(dá)式時(shí)，從右到左掃描。
到此這篇關(guān)于JavaScript 解析數(shù)學(xué)表達(dá)式的過程詳解的文章就介紹到這了,更多相關(guān)js解析表達(dá)式內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
JMenuTab簡單使用說明參數(shù)2008-03-03
在 TypeScript 中,!?和???是兩個(gè)非常重要且常用的操作符,分別用于非空斷言和可選鏈操作,下面就來具體介紹一下如何使用,具有一定的參考價(jià)值,感興趣的可以了解一下2025-02-02
Java與JavaScript中判斷兩字符串是否相等的區(qū)別
這篇文章主要介紹了Java與JavaScript中判斷兩字符串是否相等的區(qū)別,非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2017-03-03
canvas實(shí)現(xiàn)粒子時(shí)鐘效果
本文將使用canvas實(shí)現(xiàn)粒子時(shí)鐘效果，具有一定的參考價(jià)值，下面跟著小編一起來看下吧2017-02-02
JS實(shí)現(xiàn)漢字與Unicode碼相互轉(zhuǎn)換的方法詳解
這篇文章主要介紹了JS實(shí)現(xiàn)漢字與Unicode碼相互轉(zhuǎn)換的方法,結(jié)合實(shí)例形式較為詳細(xì)的分析了javascript針對漢字與Unicode編碼轉(zhuǎn)換的操作技巧與相關(guān)注意事項(xiàng),需要的朋友可以參考下2017-04-04
本篇文章主要介紹了redux中間件之redux-thunk的具體使用，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-04-04
JavaScript數(shù)組各種常見用法實(shí)例分析
這篇文章主要介紹了JavaScript數(shù)組各種常見用法實(shí)例分析,包括數(shù)組的添加、刪除、替換、還原等常見技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-08-08
JavaScript的面向?qū)ο?二)...2006-11-11
JS數(shù)組實(shí)現(xiàn)分類統(tǒng)計(jì)實(shí)例代碼
本文通過實(shí)例代碼給大家介紹了js數(shù)組實(shí)現(xiàn)分類統(tǒng)計(jì)的相關(guān)知識，非常不錯(cuò)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2018-09-09
這篇文章主要給大家介紹了關(guān)于JS中Math對象使用的相關(guān)資料,Math和其他的對象不同,它不是一個(gè)構(gòu)造函數(shù),它屬于一個(gè)工具類,不用創(chuàng)建對象,它里面封裝了數(shù)學(xué)運(yùn)算相關(guān)的屬性和方法,需要的朋友可以參考下2024-06-06