2

编辑：具有交互性的完整代码：http: //jsfiddle.net/LDEGe/2/

我是一名高中 CS 入门学生，作为与课堂无关的副项目，我正在尝试使用 Shunting-Yard 算法创建一个简单的数学方程解析器。我理解这里的伪代码，但我无法将其转换为 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;
}

最后，我有分流算法，我认为它遵循了这里的伪代码

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

您可以将字符串轻松分解为 Tokens，如下所示：如果生成 Tokens 的代码是正确的，则跳到下一个代码以使用 Shutting 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 函数返回的 Tokens 列表，就可以使用 Shutting 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;
  }
}

最后我们准备好转换为后缀：

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 回答