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