Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save Olegas/5744664 to your computer and use it in GitHub Desktop.
Save Olegas/5744664 to your computer and use it in GitHub Desktop.
Experimenting on Reverse Polish notation.... Competing with @dftcdr and @dark_garret
function isOperator(c) {
return '/*+-^'.indexOf(c) != -1;
}
function peek(stack) {
return stack[stack.length - 1];
}
var doOper = {
'+': function(a, b) {
return a + b;
},
'-': function(a, b) {
return a - b;
},
'*': function(a, b) {
return a * b;
},
'/': function(a, b) {
return a / b;
},
'^': function(a, b) {
return Math.pow(a, b);
}
};
function parse(_str) {
_str = _str.replace(/ /g, '');
var s = '', o = '', c, i = 0, opstack = [], stack = [];
var priority = {
'+': 1,
'-': 1,
'*': 2,
'/': 2,
'^': 3,
'(': 0
};
function endOp() {
if(o) {
if(opstack.length) {
var last = peek(opstack);
if(priority[o] <= priority[last]) {
stack.push(opstack.pop());
}
}
opstack.push(o);
o = '';
}
}
function endNumber() {
if(s) {
stack.push(Number(s));
s = '';
}
}
while(c = _str.charAt(i)) {
if(c == '(') {
opstack.push(c);
} else if(c == ')') {
endOp(); endNumber();
if(opstack.length) {
while(true) {
var op = opstack.pop();
if(op) {
if(op == '(') {
break;
} else {
stack.push(op);
}
}
else
throw "Unmatched rbrace";
}
} else {
throw "Unmatched rbrace";
}
} else if('0' <= c && c <= '9') {
endOp();
s += c;
} else if(c == '.') {
if(s && s.indexOf('.') == -1) {
s += c;
} else {
throw "Unexpected .";
}
} else if(isOperator(c)) {
endNumber();
o = c;
endOp();
} else
throw "Unknown symbol " + c;
i++;
}
endOp();
endNumber();
while(opstack.length) {
stack.push(opstack.pop());
}
return stack;
}
function calc(stack) {
var i = 0, c;
while((c = stack[i]) !== undefined) {
if(isOperator(c)) {
stack.splice(
i - 2,
3,
doOper[c](stack[i - 2], stack[i - 1]) );
i -= 2;
}
i++;
}
if(stack.length != 1)
throw "Invalid expression";
return stack.pop();
}
var ex = '(3*5-6) - ((3-3) * (5-6))';
var stack = parse(ex);
console.log(stack);
console.log(calc(stack));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment