EDIT: Complete code with interactivity: http://jsfiddle.net/LDEGe/2/
I am an introductory CS student in high school, and as a side project unrelated to the class, I'm trying to create a simple math equation parser using the Shunting-Yard Algorithm. I understand the pseudocode here, but I am having trouble converting it into Javascript code. I've created a stack and queue object here
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);
};
}
To start, I'm just using simple math operators, + - * / ^, and tokenizing the string by putting a space around each operator, then splitting it, and converting each token into an object, with the type, precedence, and associativity, like this
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;
}
to convert it to an object, I run it through this function, which just sees what the input is, and then assigns it precedence, associativity, a name, and a type
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;
}
Finally, I have the shunting algorithm, which, I thought to have followed the pseudocode 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;
}
When I tokenize and shunt something simple, like 1+1, it returns the expected 1 1 +. However, when I give it 1+1+1, it gets stuck in an infinite loop. It also has trouble recognizing close parentheses, and it will not remove all parenthesis tokens. For example, when I type in (1+1), it gives out ["1", "1", "("]. Could anyone point me to where the errors are in the algorithm, and give me some tips on how to solve it? I've looked over it several times, but I can't see where the error in handling parentheses is.
Thanks
You can break a string into Tokens easily as follows: If your code for generating Tokens is correct then skip to next code for conversion to postfix form using Shunting yard algorithm.
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();
}
Once the string is converted into a list of Tokens returned by Break function, Shunting yard algorithm can be used for conversion to postfix form:
Following subroutine returns priorities of operator:
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;
}
}
Finally we are ready for conversion to 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;
}
Now, say, if we want postfix form of "1+1+1" , we call Postfix(Break("1+1+1")). You can have a look at the running code at: http://jsbin.com/AbIleWu/1/edit?js,output
PS: You can add other unary operators like sin,cos,tan,log,ln etc. easily.