JavaScript中序表达式转后序表达式并计算结果

2019-01-17  本文已影响7人  阿昕_

为什么要转换

中序转后续

模拟栈
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]
  }
}

中序转后序的过程

模拟演示
// 中序转后序
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('|')
}

后序的计算过程

模拟演示
// 后序表达式计算得出结果
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
上一篇 下一篇

猜你喜欢

热点阅读