Проблемы с Шунтированием Yard Алгоритм

Question

EDIT: Полный код с интерактивностью: http://jsfiddle.net/LDEGe/2/

Я вводный CS студентом в средней школе, а также в качестве побочного проекта, не связанного с классом, я пытаюсь создать простой математического анализатора с использованием алгоритма Шунтин-Ярд. Я понимаю pseudocode здесь, но у меня возникли проблемы с преобразованием его в код 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); 
    }; 
} 

Для начала, я только с помощью простых математических операторов, + - */^ и tokenizing строки, помещая пространство вокруг каждый оператора, а затем разделив его, и преобразование каждого лексем в объект, с типом, старшинства и ассоциативности, как этот

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", "("]. Может ли кто-нибудь указать мне, где находятся ошибки в алгоритме, и дать мне несколько советов о том, как его решить? Я просматривал это несколько раз, но я не вижу, где ошибка при обработке круглых скобок.

Благодаря

Answer 1

Вы можете разбить строку на лексемы легко следующим образом: Если ваш код для генерации токенов правильно, то перейти к следующему коду для преобразования в форму постфикса, используя алгоритм сортировочной станции.

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(); 
} 

После строка преобразуется в список лексем, возвращаемых функцией Перерыв, алгоритм сортировочной станции может быть использован для преобразования в форме постфикса:

После функция возвращает приоритеты оператора:

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 и т. Д.