2

編集: インタラクティブな完全なコード: http://jsfiddle.net/LDEGe/2/

私は高校の CS 入門生で、クラスとは関係のないサイド プロジェクトとして、Shunting-Yard Algorithm を使用して簡単な数式パーサーを作成しようとしています。ここの疑似コードは理解できますが、Javascript コードに変換するのに問題があります。ここにスタックとキュー オブジェクトを作成しました

function Queue(){
    this.stack=new Array();
    this.dequeue=function(){
        return this.stack.pop();
    };
    this.enqueue=function(addition){
        this.stack.unshift(addition);
    };
}
function Stack(){
    this.stack=new Array();
    this.pop=function(){
        return this.stack.pop();
    };
    this.push=function(item){
        this.stack.push(item);
    };
    this.peek=function(){
        return this.stack[this.stack.length-1];
    };
    this.empty=function(){
        return (this.stack.length<1);
    };
}

まず、単純な数学演算子 を使用し、+ - * / ^各演算子の前後にスペースを入れて文字列をトークン化し、それを分割し、各トークンを次のように型、優先順位、結合性を備えたオブジェクトに変換します。

function tokenize(input){
    input=str_replace(["+","-","*","/","^","(",")"],[" + "," - "," * "," / "," ^ "," ( "," ) "],input).replace(/\s{2,}/g, ' ').trim().split(" ");
    for(var i in input){
        input[i]=new operator(input[i]);
    }
    return input;
}

オブジェクトに変換するには、この関数を実行します。この関数は、入力が何であるかを確認し、優先順位、結合性、名前、および型を割り当てます。

function operator(name){
    this.name=name;
    this.associativity="left";
    this.type="operator";
    this.precedence=1;
    if(isNumeric(name)){
        this.type="numeric";
    }
    else if(name=="("){
        this.type="open";
    }else if(name==")"){
        this.type="close";
    }else if(name=="^"){
        this.precedence=10;
        this.associativity="right";
    }else if(name=="*" || name=="/"){
        this.precedence=5;
        
    }else if(name=="+" || name=="-"){
        this.precedence=1;
    }
    var op={
        "name":this.name,
        "type":this.type,
        "associativity":this.associativity,
        "precedence":this.precedence
    };
    return op;
}

最後に、シャント アルゴリズムがあります。これは、疑似コード here に従っていると思われます。

function shunt(input){
    var operators=new Stack();
    var output=new Queue();
    
    for(var i in input){
        var token=input[i];
        console.log(token.name);
        if(token.type=="operator"){
//          console.log(token);
            while(!operators.empty() && operators.peek().type=="operator"){
                if((token.associativity=="left" && token.precedence==operators.peek()) || (token.precedence<operators.peek().precedence)){
                    output.enqueue(operators.pop().name);
                }
            }
            operators.push(token);
            
        }else if(token.type=="open"){
            console.log(token);
            operators.push(token);
        }else if(token.type=="close"){
            while (!operators.empty() && !operators.peek().type=="open") {
                output.enqueue(operators.pop().name);
            }
            operators.pop();
        }else{
            output.enqueue(token.name);
        }
        
    }
    while(!operators.empty()){
        output.enqueue(operators.pop().name);
    }
    output.stack.reverse();
    return output.stack;
}

のような単純なものをトークン化してシャントすると1+1、期待される が返され1 1 +ます。しかし、 を与えると1+1+1、無限ループに陥ります。また、閉じ括弧の認識に問題があり、すべての括弧トークンを削除するわけではありません。たとえば、 と入力すると(1+1)、 が出力され["1", "1", "("]ます。誰かがアルゴリズムのどこにエラーがあるかを教えてくれますか?それを解決する方法についてのヒントを教えてください。何度か見直したのですが、括弧の扱いのどこが間違っているのかわかりません。

ありがとう

4

1 に答える 1

1

次のように、文字列をトークンに簡単に分割できます。トークンを生成するコードが正しい場合は、Shunting yard アルゴリズムを使用して後置形式に変換する次のコードに進みます。

function Break(expression){  /*Expression is string like "2.22+3-5"*/
  var Tokens=[];
  //Start at the end of the string//
  var i=expression.length-1;
  var Operators=['+','-','*','/','^','(',')'];
  while(i>=0){
    if(Operators.indexOf(expression[i])!=-1 && expression[i]!='-'){
      Tokens.push(expression[i]);
      i-=1;
    }
    else if(expression[i]=='-'){
      if(i===0){
        Tokens.push('neg');
        i-=1;
      }
      else if(expression[i-1]!=')' && Operators.indexOf(expression[i-1])!=-1  ){
        Tokens.push('neg');
        i-=1;
      }
      else{
        Tokens.push('-');
        i-=1;
      }
    }
    else{
      var x=0,wt=0;
      while(i>=0 && Operators.indexOf(expression[i])==-1){
        if(expression[i]=='.'){
          x=x/Math.pow(10,wt);
          i-=1;
          wt=0;
        }
        else{
          x+=Math.floor(expression[i])*Math.pow(10,wt);
          wt+=1;
          i-=1;
        }
      }
      Tokens.push(x);
    }
  }
  return Tokens.reverse();
}

文字列が Break 関数によって返されるトークンのリストに変換されると、Shunting yard アルゴリズムを使用して後置形式に変換できます。

次のサブルーチンは、演算子の優先度を返します。

function Priority(x){
  switch(x){
    case 'neg': /*Highest priority of unary negation operator*/
      return 4;
    case '^':
      return 3;
    case '/':
      return 2;
    case '*':
      return 2;
    case '+':
      return 1;
    case '-':
      return 1;
    case '(':
      return 0;
  }
}

最後に、postfix への変換の準備が整いました。

function Postfix(Tokens){
  var Stack=[],List=[];
  var Operators=['^','/','*','+','-'];
  var i;
  for(i=0;i<Tokens.length;i++){
    if(Operators.indexOf(Tokens[i])!=-1){
      while(Stack.length!=-1 && Priority(Stack[Stack.length-1])>=Priority(Tokens[i]))
        List.push(Stack.pop());
      Stack.push(Tokens[i]);
    }
    else if(Tokens[i]=='(')
      Stack.push(Tokens[i]);
    else if(Tokens[i]==')'){
      while(Stack[Stack.length-1]!='(')
        List.push(Stack.pop());
      Stack.pop();
    }
    else
      List.push(Tokens[i]);
  }
  while(Stack.length!==0)
    List.push(Stack.pop());
  return List;
}

たとえば、 "1+1+1" の後置形式が必要な場合は、Postfix(Break("1+1+1")) を呼び出します。実行中のコードはhttp://jsbin.com/AbIleWu/1/edit?js,outputで確認できます。

PS: sin、cos、tan、log、ln などの他の単項演算子を簡単に追加できます。

于 2013-11-20T18:22:10.543 に答える