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