JavaScript实现中序表达式转逆波兰表达式
中缀表达式: 1 + 5 * 3 + (6 - 2) / 2 - 4 输入['1', '+', '5', '', '3', '+', '(', '6', '-', '2', ')', '/', '2', '-', '4'] 输出[ '1', '5', '3', '', '+', '6', '2', '-', '2', '/', '+', '4', '-' ]
function toPPN(origin) {
'use strict'
if (Object.prototype.toString.call(origin) !== '[object Array]') {
console.error('非法输入, 请输入格式正确的中缀表达式数组')
return []
}
let ppn = [], operator = [];
// 遍历中缀表达式转换成的数组
for (let i = 0; i < origin.length; i++) {
const item = origin[i]
// 校验原始输入的元素是否符合要求
if (isNaN(item) && (['+', '-', '*', '/', '(', ')']).indexOf(item) < 0){
console.error('中缀表达式的组成元素不符合规则, 请检查修正')
return []
}
// 判断该位置上的元素是否为数字
if (!isNaN(item)) {
// 如果是数字, item推入ppn
ppn.push(item)
} else if (item === '(' || operator.length === 0) {
// 如果是'('或者operator为空数组, item推入operator
operator.push(item)
} else if (item === ')') {
// 如果是')', operator从末尾弹出运算符并推入ppn直到'('
do {
ppn.push(operator.pop())
} while (operator[operator.length - 1] !== '(')
// operator弹出'('
operator.pop()
} else if (!needPop(item, operator[operator.length - 1])) {
operator.push(item)
} else {
// 比较运算符的优先级, 如果item低于operator栈顶符号优先级, operator弹出尾元素并推入到ppn
while (operator.length && needPop(item, operator[operator.length - 1])) {
ppn.push(operator.pop())
}
operator.push(item)
}
}
// 最后, 逐次弹出operator尾元素入栈到ppn
while (operator.length) {
ppn.push(operator.pop())
}
return ppn
}
function needPop(a, b) {
// b: operator的尾元素
if (b === '(') return false
if ((a === '*' || a === '/') && (b === '+' || b === '-')) return false
return true
}
相关文章
- webpack相关知识
能够处理JS文件的互相依赖关系 能够处理JS的兼容问题 安装 全局安装 npm install webpack -g 项目安装 npm install webpack --save-
- Javascript基础和ES6
HTML的基础事件 onmouseover、onmouseout表示JS事件的鼠标移入鼠标移出 document.getElementById('id') JS中选择HTML的ID元素<in
- JavaScript编码规则
JavaScript编码规则 目的:改善协作编码、代码质量。 var 声明变量必须用var。 防止变量变为全局变量,污染全局环境。 常量 基本类型number、string、boolean是常量值。对
- JavaScript获取和设置CSS属性
获取样式 元素对象的宽高位置距离等属性 如offsetWidht、cilentWidht、scrollWidth…… let oWidth=obj.offsetWidth; 注意: 只能获取属
- javascript作用域、上下文、this和闭包详解
词法作用域lexical scope 定义在词法阶段的作用域。词法作用域是变量和语句块在定义时所处的位置决定的。 全局 块级:在{}之内是一个块级作用域(ES6之前没有块级作用于只有函数内的局部作用
随机推荐
- webpack相关知识
能够处理JS文件的互相依赖关系 能够处理JS的兼容问题 安装 全局安装 npm install webpack -g 项目安装 npm install webpack --save-
- Javascript基础和ES6
HTML的基础事件 onmouseover、onmouseout表示JS事件的鼠标移入鼠标移出 document.getElementById('id') JS中选择HTML的ID元素<in
- JavaScript编码规则
JavaScript编码规则 目的:改善协作编码、代码质量。 var 声明变量必须用var。 防止变量变为全局变量,污染全局环境。 常量 基本类型number、string、boolean是常量值。对
- JavaScript获取和设置CSS属性
获取样式 元素对象的宽高位置距离等属性 如offsetWidht、cilentWidht、scrollWidth…… let oWidth=obj.offsetWidth; 注意: 只能获取属
- javascript作用域、上下文、this和闭包详解
词法作用域lexical scope 定义在词法阶段的作用域。词法作用域是变量和语句块在定义时所处的位置决定的。 全局 块级:在{}之内是一个块级作用域(ES6之前没有块级作用于只有函数内的局部作用