為什么要轉(zhuǎn)換

• 中序表達(dá)式：10(8-21)*2-30
• 后序表達(dá)式： 10821-2*30-
• 中序表達(dá)式是給人看的，可以直觀的根據(jù)優(yōu)先級計(jì)算出結(jié)果，但是計(jì)算機(jī)無法自動(dòng)識別優(yōu)先級，因此將帶有計(jì)算的優(yōu)先級和括號的中序表達(dá)式變成符合某文法的后序（或前序）表達(dá)式之后，計(jì)算機(jī)可以通過從左到右（或從右到左）掃描來計(jì)算結(jié)果。

中序轉(zhuǎn)后續(xù)

模擬棧

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]
  }
}

中序轉(zhuǎn)后序的過程

• 處理表達(dá)式：10*(8-2*1)*2-30 處理結(jié)果為 ["10", "*", "(", "8", "-", "2", "*", "1", ")", "*", "2", "-", "30"]
• 遍歷處理過后的中序表達(dá)式
• 遇到數(shù)字直接入棧
• 遇到'(' 直接入棧
• 遇到 ')' 則持續(xù)出棧至遇到'('停止
• 如果 （棧為空 || 當(dāng)前運(yùn)算符優(yōu)先級較高 || 棧頂是'('字符 ）則入棧
• 否則 棧頂元素依次出棧 直至新操作符比棧頂優(yōu)先級高 新操作符入棧
• 遍歷結(jié)束 輸出棧中所有元素

模擬演示

• 只要后來的優(yōu)先級沒有高于棧頂?shù)?就把棧頂?shù)牟僮鞣贸鰜碇钡胶髞淼膬?yōu)先級高于棧頂?shù)臑橹?只有遇到右括號的時(shí)候需要一直往外拿 直到碰到左括號
• 處理結(jié)果arr = ["10", "*", "(", "8", "-", "2", "*", "1", ")", "*", "2", "-", "30"]
• 暫時(shí)存儲后序表達(dá)式的數(shù)組A，存儲操作符的模擬棧B
• 遍歷arr
• "10"：數(shù)字 -- 存入A -- A ['10']
• *：操作符 --入棧B -- B ['*']
• (：操作符 --入棧B -- B ['*', '(']
• "8"：數(shù)字 -- 存入A -- A ['10', '8']
• -：操作符 --入棧B -- B ['*', '(', '-']
• "2"：數(shù)字 -- 存入A -- A ['10', '8', '2']
• *：操作符 --入棧B -- B ['*', '(', '-','*']
• "1"：數(shù)字 -- 存入A -- A ['10', '8', '2', '1']
• )：操作符 --B開始出棧并存入A 直至(出現(xiàn)
  B ['*', '(', '-'] A ['10', '8', '2', '1', '*']
B ['*', '('] A ['10', '8', '2', , '1','*', '-']
B ['*'] A ['10', '8', '2', '1', '*', '-']
• *：操作符 --優(yōu)先級不高于棧頂?shù)?' 所以棧頂出棧存入A 新的 ''入棧
  B [] A ['10', '8', '2', '1', '*'', '-', '*']
B ['*'] A ['10', '8', '2', '1', '*', '-', '*']
• "2"：數(shù)字 -- 存入A -- A ['10', '8', '2', '1', '*', '-', '*', '2']
• -：操作符 --優(yōu)先級不高于棧頂?shù)?*' 所以棧頂出棧存入A 新的 '-'入棧
  B [] A ['10', '8', '2', '1', '*', '-', '*', '2', '*']
B ['-'] A ['10', '8', '2', '1', '*', '-', '*', '2', '*']
• "30"：數(shù)字 -- 存入A -- A ['10', '8', '2', '1', '*', '-', '*', '2', '*', '30']
• 遍歷結(jié)束 棧B不為空 依次出棧
  B [] A ['10', '8', '2', '1', '*', '-', '*', '2', '*', '30', '-']
• 結(jié)束 得到轉(zhuǎn)換后的后序數(shù)組['10', '8', '2', '1', '*', '-', '*', '2', '*', '30', '-']

// 中序轉(zhuǎn)后序
function transform(str) {
  // 模擬棧 存儲運(yùn)算操作符
  var stack = new Stack()
  // 后序表達(dá)式數(shù)組
  var postfixExp = []
  // 切分中序表達(dá)式
  str = this.str2arr(str)
  // 遍歷處理過后的中序表達(dá)式
  for (let i = 0; i < str.length; i++) {
    // debugger
    let item = str[i]
    if(!isNaN(Number(item))) { // 數(shù)字直接入棧
      postfixExp.push(item)
    } else if (item === '(') { // '(' 直接入棧
      stack.in(item)
    } else if (item === ')') { // 遇到 ')' 則持續(xù)出棧至遇到'('停止
      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() === '(') {
        // 棧為空 || 當(dāng)前運(yùn)算符優(yōu)先級較高 || 棧頂是'('字符 
        stack.in(item)
      } else {
        // 棧頂元素依次出棧 直至新操作符比棧頂優(yōu)先級高 新操作符入棧
        let top = stack.last() // 目前棧頂?shù)脑?        let max = stack.opts[item] // 新操作符的權(quán)重
        while(top && max <= stack.max && stack.last() !== '(') {
          postfixExp.push( stack.out() )
          top = stack.last()
        }
        stack.in(item)
      }
    }
  }
  
  // 遍歷結(jié)束 輸出棧中所有?元素
  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('|')
}

后序的計(jì)算過程

• 遍歷后序表達(dá)式數(shù)組
• 遇到數(shù)字入棧
• 遇到操作符 則拿出棧頂?shù)膬蓚€(gè)元素 進(jìn)行運(yùn)算 并將運(yùn)算結(jié)果入棧
• 遍歷結(jié)束時(shí)棧中的元素為運(yùn)算結(jié)果

模擬演示

• 后序表達(dá)式數(shù)組：A ['10', '8', '2', '1', '*', '-', '*', '2', '*', '30', '-']
• 存儲運(yùn)算數(shù)的模擬棧B
• 遍歷A
• "10"：數(shù)字 -- 入棧B -- B ['10']
• "8"：數(shù)字 -- 入棧B -- B ['10', '8']
• "2"：數(shù)字 -- 入棧B -- B ['10', '8', '2']
• "1"：數(shù)字 -- 入棧B -- B ['10', '8', '2', '1']
• "*"：運(yùn)算符 -- 取出棧B最上邊的兩個(gè)元素 '1' 和'2'
  運(yùn)算 2 * 1 = 2
  運(yùn)算結(jié)果入棧B B ['10', '8', '2']
• "-"：運(yùn)算符 -- 取出棧B最上邊的兩個(gè)元素 '2' 和'8'
  運(yùn)算 8 - 2 = 6
  運(yùn)算結(jié)果入棧B B ['10', '6']
• "*"：運(yùn)算符 -- 取出棧B最上邊的兩個(gè)元素 '6' 和'10'
  運(yùn)算 10 * 6 = 60
  運(yùn)算結(jié)果入棧B B ['60']
• "2"：數(shù)字 -- 入棧B -- B ['60','2']
• "*"：運(yùn)算符 -- 取出棧B最上邊的兩個(gè)元素 '2' 和'60'
  運(yùn)算 60 * 2 = 120
  運(yùn)算結(jié)果入棧B B ['120']
• "30"：數(shù)字 -- 入棧B -- B ['120', '30']
• "-"：運(yùn)算符 -- 取出棧B最上邊的兩個(gè)元素 '30' 和'120'
  運(yùn)算 120 - 30 = 90
  運(yùn)算結(jié)果入棧B B ['90']
• 遍歷結(jié)束 結(jié)果為棧B中的元素 90

// 后序表達(dá)式計(jì)算得出結(jié)果
function getResult(arr) {
  // 模擬棧 存儲運(yùn)算數(shù)字
  let stack = new Stack()
  for (let i = 0; i < arr.length; i++) {
    let item = arr[i]
    if(!isNaN(Number(item))) { // 數(shù)字直接入棧
      stack.in(item)
    } else { // 遇到操作符 則拿出棧頂?shù)膬蓚€(gè)元素 進(jìn)行運(yùn)算 并將運(yùn)算結(jié)果入棧
      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()
}

運(yùn)算結(jié)果打印

var InfixExp = '10*(8-2*1)*2-30'
var postfixExp = transform(InfixExp)
console.log(InfixExp,'的后序表達(dá)式--', postfixExp.join(''));
var result = getResult(postfixExp)
console.log('后序表達(dá)式--', postfixExp.join(''), '的計(jì)算結(jié)果是：', result);

運(yùn)算結(jié)果打印1

運(yùn)算結(jié)果打印2

運(yùn)算結(jié)果打印3