Skip to content

Instantly share code, notes, and snippets.

@bitnenfer
Last active August 29, 2015 14:09
Show Gist options
  • Save bitnenfer/205384c8c12687021001 to your computer and use it in GitHub Desktop.
Save bitnenfer/205384c8c12687021001 to your computer and use it in GitHub Desktop.
This is a infix to postfix expression translator.
/*
* This was created out of my own study
* of lexical analysis and expression
* parsing.
*
* Demo at: http://dev.shin.cl/infixtopostfix/
*
* @author Felipe Alfonso
*/
(function (scope) {
'use strict';
var presedence = function (value) {
if (typeof value === 'undefined') {
return 0;
}
switch (value) {
case '(':
case ')':
return 3;
break;
case '*':
case '/':
return 2;
break;
case '+':
case '-':
return 1;
break;
default:
return 0;
break;
}
},
flush = function (stack, result) {
while (stack.length) {
var token = stack.pop();
if (token !== '(' && token !== ')') {
result += token + ' ';
}
}
return result;
},
isOperator = function (value) {
return typeof value === 'string' && value.match(/\+|\-|\*|\/|\(|\)/g) !== null;
},
isOperand = function (value) {
return typeof value === 'string' && value.match(/([a-zA-Z]|[.0-9]+)/g) !== null;
},
infixToPostfix = function (expression) {
var index = 0,
stack = [],
result = '',
length,
operand = '';
if (typeof expression !== 'string') {
return '';
}
for (index, length = expression.length; index < length; index++) {
if (isOperand(expression[index])) {
operand = '';
while (isOperand(expression[index]) && !isOperator(expression[index])) {
operand += expression[index] + '';
index++;
}
index--;
result += operand + ' ';
} else if (isOperator(expression[index])) {
if ((presedence(stack[stack.length - 1]) >= presedence(expression[index]) &&
stack[stack.length - 1] !== '(') ||
expression[index] === ')') {
result = flush(stack, result);
}
stack.push(expression[index]);
}
}
return flush(stack, result);
};
scope.infixToPostfix = infixToPostfix;
}(typeof exports !== 'undefined' ? exports : window));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment