为什么要转换
- 中序表达式：10(8-21)*2-30
- 后序表达式： 10821-2*30-
- 中序表达式是给人看的，可以直观的根据优先级计算出结果，但是计算机无法自动识别优先级，因此将带有计算的优先级和括号的中序表达式变成符合某文法的后序（或前序）表达式之后，计算机可以通过从左到右（或从右到左）扫描来计算结果。
中序转后续
模拟栈
class Stack {
constructor() {
this.stack = []
this.max = 0
this.opts = {
'+': 1,
'-': 1,
'*': 5,
'/': 5,
'(': 10,
')': 10
}
}
in(char) {
this.stack.push(char)
this.max = this.opts[this.stack[this.stack.length - 1]]
}
out() {
let pop = this.stack.pop()
this.max = this.opts[this.stack[this.stack.length - 1]]
return pop
}
empty() {
return !this.stack.length
}
last() {
return this.stack[this.stack.length - 1]
}
}
中序转后序的过程
- 处理表达式：
10*(8-2*1)*2-30处理结果为["10", "*", "(", "8", "-", "2", "*", "1", ")", "*", "2", "-", "30"] - 遍历处理过后的中序表达式
- 遇到数字直接入栈
- 遇到'(' 直接入栈
- 遇到 ')' 则持续出栈至遇到'('停止
- 如果 （栈为空 || 当前运算符优先级较高 || 栈顶是'('字符 ）则入栈
- 否则 栈顶元素依次出栈 直至新操作符比栈顶优先级高 新操作符入栈
- 遍历结束 输出栈中所有元素
模拟演示
- 只要后来的优先级没有高于栈顶的 就把栈顶的操作符拿出来直到后来的优先级高于栈顶的为止 只有遇到右括号的时候需要一直往外拿 直到碰到左括号
- 处理结果
arr = ["10", "*", "(", "8", "-", "2", "*", "1", ")", "*", "2", "-", "30"] - 暂时存储后序表达式的数组A，存储操作符的模拟栈B
- 遍历arr
-
"10"：数字 -- 存入A --A ['10'] -
*：操作符 --入栈B --B ['*'] -
(：操作符 --入栈B --B ['*', '('] -
"8"：数字 -- 存入A --A ['10', '8'] -
-：操作符 --入栈B --B ['*', '(', '-'] -
"2"：数字 -- 存入A --A ['10', '8', '2'] -
*：操作符 --入栈B --B ['*', '(', '-','*'] -
"1"：数字 -- 存入A --A ['10', '8', '2', '1'] -
)：操作符 --B开始出栈并存入A 直至(出现
B ['*', '(', '-'] A ['10', '8', '2', '1', '*']
B ['*', '('] A ['10', '8', '2', , '1','*', '-']
B ['*'] A ['10', '8', '2', '1', '*', '-'] -
*：操作符 --优先级不高于栈顶的'' 所以栈顶出栈存入A 新的 ''入栈
B [] A ['10', '8', '2', '1', '*'', '-', '*']
B ['*'] A ['10', '8', '2', '1', '*', '-', '*'] -
"2"：数字 -- 存入A --A ['10', '8', '2', '1', '*', '-', '*', '2'] -
-：操作符 --优先级不高于栈顶的'*' 所以栈顶出栈存入A 新的 '-'入栈
B [] A ['10', '8', '2', '1', '*', '-', '*', '2', '*']
B ['-'] A ['10', '8', '2', '1', '*', '-', '*', '2', '*'] -
"30"：数字 -- 存入A --A ['10', '8', '2', '1', '*', '-', '*', '2', '*', '30'] - 遍历结束 栈B不为空 依次出栈
B [] A ['10', '8', '2', '1', '*', '-', '*', '2', '*', '30', '-'] - 结束 得到转换后的后序数组
['10', '8', '2', '1', '*', '-', '*', '2', '*', '30', '-']
// 中序转后序
function transform(str) {
// 模拟栈 存储运算操作符
var stack = new Stack()
// 后序表达式数组
var postfixExp = []
// 切分中序表达式
str = this.str2arr(str)
// 遍历处理过后的中序表达式
for (let i = 0; i < str.length; i++) {
// debugger
let item = str[i]
if(!isNaN(Number(item))) { // 数字直接入栈
postfixExp.push(item)
} else if (item === '(') { // '(' 直接入栈
stack.in(item)
} else if (item === ')') { // 遇到 ')' 则持续出栈至遇到'('停止
let top = stack.out()
while (top && top !== '(') {
postfixExp.push(top)
top = stack.out()
}
}else if (stack.opts[item]) { // 合法的 加减乘除字符
if (stack.empty() || stack.opts[item] > stack.max || stack.last() === '(') {
// 栈为空 || 当前运算符优先级较高 || 栈顶是'('字符
stack.in(item)
} else {
// 栈顶元素依次出栈 直至新操作符比栈顶优先级高 新操作符入栈
let top = stack.last() // 目前栈顶的元素
let max = stack.opts[item] // 新操作符的权重
while(top && max <= stack.max && stack.last() !== '(') {
postfixExp.push( stack.out() )
top = stack.last()
}
stack.in(item)
}
}
}
// 遍历结束 输出栈中所有�元素
while(!stack.empty()) {
postfixExp.push( stack.out() )
}
return postfixExp
}
function str2arr(str) {
str = str.split('+').join('|+|')
str = str.split('-').join('|-|')
str = str.split('*').join('|*|')
str = str.split('/').join('|/|')
str = str.split('(').join('(|')
str = str.split(')').join('|)')
return str.split('|')
}
后序的计算过程
- 遍历后序表达式数组
- 遇到数字入栈
- 遇到操作符 则拿出栈顶的两个元素 进行运算 并将运算结果入栈
- 遍历结束时栈中的元素为运算结果
模拟演示
- 后序表达式数组：
A ['10', '8', '2', '1', '*', '-', '*', '2', '*', '30', '-'] - 存储运算数的模拟栈B
- 遍历A
-
"10"：数字 -- 入栈B --B ['10'] -
"8"：数字 -- 入栈B --B ['10', '8'] -
"2"：数字 -- 入栈B --B ['10', '8', '2'] -
"1"：数字 -- 入栈B --B ['10', '8', '2', '1'] -
"*"：运算符 -- 取出栈B最上边的两个元素'1' 和'2'
运算 2 * 1 = 2
运算结果入栈BB ['10', '8', '2'] -
"-"：运算符 -- 取出栈B最上边的两个元素'2' 和'8'
运算 8 - 2 = 6
运算结果入栈BB ['10', '6'] -
"*"：运算符 -- 取出栈B最上边的两个元素'6' 和'10'
运算 10 * 6 = 60
运算结果入栈BB ['60'] -
"2"：数字 -- 入栈B --B ['60','2'] -
"*"：运算符 -- 取出栈B最上边的两个元素'2' 和'60'
运算 60 * 2 = 120
运算结果入栈BB ['120'] -
"30"：数字 -- 入栈B --B ['120', '30'] -
"-"：运算符 -- 取出栈B最上边的两个元素'30' 和'120'
运算 120 - 30 = 90
运算结果入栈BB ['90'] - 遍历结束 结果为栈B中的元素 90
// 后序表达式计算得出结果
function getResult(arr) {
// 模拟栈 存储运算数字
let stack = new Stack()
for (let i = 0; i < arr.length; i++) {
let item = arr[i]
if(!isNaN(Number(item))) { // 数字直接入栈
stack.in(item)
} else { // 遇到操作符 则拿出栈顶的两个元素 进行运算 并将运算结果入栈
let tempRes = 0
let a = Number(stack.out())
let b = Number(stack.out())
switch (item) {
case '+': tempRes = b + a; break;
case '-': tempRes = b - a; break;
case '*': tempRes = b * a; break;
case '/': tempRes = b / a; break;
default : throw new Error('操作符有误')
}
stack.in(tempRes)
}
}
return stack.out()
}
运算结果打印
var InfixExp = '10*(8-2*1)*2-30'
var postfixExp = transform(InfixExp)
console.log(InfixExp,'的后序表达式--', postfixExp.join(''));
var result = getResult(postfixExp)
console.log('后序表达式--', postfixExp.join(''), '的计算结果是：', result);
运算结果打印1
运算结果打印2
运算结果打印3
