DIV CSS 佈局教程網

JavaScript 實作四則運算表達式解析演算法
編輯:關於JavaScript     

撰寫程式時,我們偶爾會遇到需要自行解析四則運算表達式的情況。本文簡單介紹如何以 JavaScript 實現對簡單四則運算表達式的解析。

一、熟悉概念

中綴表示法(中綴記法)是最通用的算術或邏輯公式表示方式,運算子以中綴形式位於運算元中間(例如 3 + 4)。這就是我們最常用的算術表達式,中綴表達式對人類而言較易理解,卻不利於電腦解析。

逆波蘭表示法(Reverse Polish Notation,RPN,又稱後綴表示法),是由波蘭數學家揚·武卡謝維奇於 1920 年引入的數學表達式方式。在逆波蘭記法中,所有運算子置於運算元之後,因此不需括號來標示運算子的優先級。逆波蘭表示法容易搭配堆疊結構進行解析與計算,所以我們解析四則運算表達式的策略是:先把中綴表達式轉換為逆波蘭表達式,再計算其值。

二、轉換流程

中綴表達式轉後綴表達式(調度場演算法):

1. 從輸入佇列彈出一個記號;2. 若為數字,加入輸出佇列;3. 若為運算子(+-*/),則與輸出堆疊頂端的運算子比較,若優先級小於或等於棧頂運算子,就將棧頂運算子彈出並加入輸出佇列(循環直到條件不滿足),最後把本次運算子壓入堆疊;4. 若為左括號,壓入堆疊;5. 若為右括號,不斷從堆疊彈出運算子並加入輸出佇列,直到棧頂為左括號,彈出左括號但不加入輸出佇列,若找不到左括號則說明括號不對稱;6. 若輸入佇列為空而堆疊尚有運算子,若棧頂為左括號則表示括號不匹配,否則將棧中運算子逐一彈出加入輸出佇列;7. 完成。

三、轉換程式碼實現

function isOperator(value){
  var operatorString = "+-*/()";
  return operatorString.indexOf(value) > -1;
}
function getPrioraty(value){
  switch(value){
    case '+':
    case '-': return 1;
    case '*':
    case '/': return 2;
    default: return 0;
  }
}
function prioraty(o1, o2){
  return getPrioraty(o1) <= getPrioraty(o2);
}
function dal2Rpn(exp){
  var inputStack = [];
  var outputStack = [];
  var outputQueue = [];
  for(var i = 0, len = exp.length; i < len; i++){
    var cur = exp[i];
    if(cur != ' '){
      inputStack.push(cur);
    }
  }
  while(inputStack.length > 0){
    var cur = inputStack.shift();
    if(isOperator(cur)){
      if(cur == '('){
        outputStack.push(cur);
      } else if(cur == ')'){
        var po = outputStack.pop();
        while(po != '(' && outputStack.length > 0){
          outputQueue.push(po);
          po = outputStack.pop();
        }
        if(po != '('){
          throw "error: unmatched ()";
        }
      } else {
        while(prioraty(cur, outputStack[outputStack.length - 1]) && outputStack.length > 0){
          outputQueue.push(outputStack.pop());
        }
        outputStack.push(cur);
      }
    } else {
      outputQueue.push(new Number(cur));
    }
  }
  if(outputStack.length > 0){
    if(outputStack[outputStack.length - 1] == ')' || outputStack[outputStack.length - 1] == '('){
      throw "error: unmatched ()";
    }
    while(outputStack.length > 0){
      outputQueue.push(outputStack.pop());
    }
  }
  return outputQueue;
}
console.log(dal2Rpn('1 + 2'));
console.log(dal2Rpn('1 + 2 + 3'));
console.log(dal2Rpn('1 + 2 * 3'));
console.log(dal2Rpn('1 + 2 * 3 - 4 / 5'));
console.log(dal2Rpn('( 1 + 2 )'));
console.log(dal2Rpn('( 1 + 2 ) * ( 3 - 4 ) / 5'));
console.log(dal2Rpn('( 1 + 2 ) * (( 3 - 4 ) / 5)'));

四、逆波蘭表達式求值

1. 從輸入佇列彈出一個記號;2. 若為運算元,加入輸出堆疊;3. 若為運算子,從輸出堆疊彈出兩個運算元進行計算,並把結果壓回堆疊;4. 循環操作,若輸入佇列為空且輸出堆疊只剩一個數,該數即為結果,否則表示出現了多餘的運算元。

五、計算程式碼

function evalRpn(rpnQueue){
  var outputStack = [];
  while(rpnQueue.length > 0){
    var cur = rpnQueue.shift();
    if(!isOperator(cur)){
      outputStack.push(cur);
    } else {
      if(outputStack.length < 2){
        throw "unvalid stack length";
      }
      var sec = outputStack.pop();
      var fir = outputStack.pop();
      outputStack.push(getResult(fir, sec, cur));
    }
  }
  if(outputStack.length != 1){
    throw "unvalid expression";
  } else {
    return outputStack[0];
  }
}

六、結語

逆波蘭表示法初次接觸時會不太習慣,但熟悉之後會發現思路其實特別簡單。不像中綴表示法還要處理各種優先級、小括號等麻煩的邏輯,逆波蘭表示法完全不用考慮優先級,也沒有大小括號來攪局,顯得格外簡潔。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved