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ù)學表達式，被拆解為上面的四個原則，即是我們需要解決的問題。所以在遇到一個大的問題時，我們第一步應該是對問題進行拆解。
在對一個個小問題進行解答的時候，我們就把一個大的問題解決了。
下面逐一解決這四個問題。
解決問題
從左到右計算
從左到右計算，有兩個關(guān)鍵點從左到右和計算。
計算
我們先分析計算，在進行+ - * /計算時，即利用運算符號對兩側(cè)數(shù)字進行運算。下面用一個圖表示下1+2
這樣就確定了一個運算操作的基本數(shù)據(jù)結(jié)構(gòu)，即二叉??。中間節(jié)點存儲運算符號，left節(jié)點儲存左側(cè)的數(shù)值，right節(jié)點存儲右邊的數(shù)值。
從左到右
這里舉一個簡單的加法運算表達式1 + 2 + 3 + 4來分析從左到右。我們從左到右遍歷這個這個表達式，可以得到下圖二叉??。
但是遍歷這樣的數(shù)據(jù)結(jié)構(gòu)得到的運算過程是從右到左（深度遍歷先計算 3 + 4 一直到 1）。所以我們嘗試從右到左遍歷這個表達式，可以得到下圖。
現(xiàn)在我們就明確了編碼需要做的具體事項，即從右到左遍歷表達式，形成一個二叉??。基本的代碼如下：
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é)構(gòu)敏感的同學，一定會想到棧。
同時我們要記錄下(、)位置信息。
我們調(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)化代碼，分析代碼中重復的工作等等
同時我們也要拓展編程相關(guān)基本知識，不斷學習。這樣在面對問題時，可以快速想到可能的解決方案。 例如上面的問題，同學對數(shù)據(jù)結(jié)構(gòu)有所了解的話，則分析小括號可以迅速想到用棧去解決。另外一點就是編譯原理中也有講到掃描運算表達式時，從右到左掃描。
到此這篇關(guān)于JavaScript 解析數(shù)學表達式的過程詳解的文章就介紹到這了,更多相關(guān)js解析表達式內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
JavaScript實現(xiàn)簡單獲取本地圖片主色調(diào)
想象一個場景，就是如何根據(jù)一張圖片大概提取出它的主色調(diào)呢？獲取主色調(diào)后，可能會用來設置某些背景顏色，這里，利用?JS?簡單獲取本地圖片主色調(diào)，希望對大家有所幫助2023-03-03
這篇文章主要給大家介紹了ES5和ES6中類的區(qū)別的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-12-12
三劍客：offset、client和scroll還傻傻分不清？
這篇文章主要給大家介紹了三劍客：offset，client和scroll的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-12-12
這篇文章主要介紹了js實現(xiàn)超簡單的展開、折疊目錄代碼,通過javascript操作鼠標點擊事件控制頁面元素樣式的動態(tài)改變實現(xiàn)該功能,非常簡單實用,需要的朋友可以參考下2015-08-08
用js控制css樣式，能讓網(wǎng)頁達到良好的的用戶體驗甚至是動畫的效果。并且考慮到效率。2009-10-10
這篇文章主要為大家詳細介紹了一個簡易的js圖片輪播效果，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-07-07
這篇文章主要介紹了JavaScript裝飾者模式原理與用法,結(jié)合實例形式總結(jié)分析了JavaScript裝飾者模式相關(guān)概念、功能、原理、用法及操作注意事項,需要的朋友可以參考下2020-03-03
這篇文章主要為大家詳細介紹了js圖片查看器的制作方法，可以實現(xiàn)圖片的滑動等效果,具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-11-11
Nuxt3?布局layouts和NuxtLayout的使用詳解
layouts是Nuxt3提供的一種方便開發(fā)者快速實現(xiàn)自定義布局的約定，是基于Vue3的一個開發(fā)框架，基于服務器端渲染SSR，可以更加方便的用于Vue的SEO優(yōu)化，這篇文章主要介紹了Nuxt3?布局layouts和NuxtLayout的使用,需要的朋友可以參考下2023-04-04
js結(jié)合css實現(xiàn)登錄后才能復制的效果實例
很多網(wǎng)站都有登錄后才能復制的限制，什么原理呢？css屬性user-select:none，通常會采用這種方式來禁止復制文本。但瀏覽開發(fā)者工具-審查元素，取消此樣式后，就可以選中文本了。想要完整地禁止復制，還需要通過js控制選擇的內(nèi)容。2023-07-07