7
\$\begingroup\$

I've written this infix to postfix converter using this website as an helper. At the end of the web page, there is the procedure for the algorithm.

A summary of the rules follows:

  1. Print operands as they arrive.

  2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto the stack.

  3. If the incoming symbol is a left parenthesis, push it on the stack.

  4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until you see a left parenthesis. Discard the pair of parentheses.

  5. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.

  6. If the incoming symbol has equal precedence with the top of the stack, use association. If the association is left to right, pop and print the top of the stack and then push the incoming operator. If the association is right to left, push the incoming operator.

  7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop the stack and print the top operator. Then test the incoming operator against the new top of stack.

  8. At the end of the expression, pop and print all operators on the stack. (No parentheses should remain.)

function InfixConverter(operators) {
    var expressionValidationRegex = /^([0-9]|\+|-|\(|\)|\*|\/|d)*$/;

    var symbolToOperatorMap = operators.reduce(function (map, obj) {
        map[obj.symbol] = obj;
        return map;
    }, {});

    this.toPostfix = function (expression) {

        if (!isExpressionValid(expression)) { throw "Expression is invalid."; }

        var operatorsStack = [], result = [];

        for (var i = 0; i < expression.length; i++) {

            var symbol = expression[i];

            if (isNumber(symbol)) {
                result.push(symbol);
                continue;
            }

            var operator = symbolToOperatorMap[symbol];
            var precedentOperator = peek(operatorsStack);

            if (precedentOperator === null) {
                operatorsStack.push(operator);
            } else if (operator.symbol === ')') {
                while (peek(operatorsStack).symbol !== '(') {
                    result.push(operatorsStack.pop().symbol);
                }

                //Remove the left parenthesis from the stack
                operatorsStack.pop();
            } else if (precedentOperator.symbol === '(' || operator.symbol === '(') {
                operatorsStack.push(operator);

            } else if (operator.priority > precedentOperator.priority) {
                operatorsStack.push(operator);

            } else if (operator.priority < precedentOperator.priority) {
                while (operatorsStack.length !== 0 && peek(operatorsStack).priority > operator.priority) {
                    result.push(operatorsStack.pop().symbol); }
                operatorsStack.push(operator);

            } else {
                if (operator.association === Associations.LeftToRight) {
                    result.push(operatorsStack.pop().symbol);
                    operatorsStack.push(operator);
                } else if (operator.association === Associations.RightToLeft) {
                    operatorsStack.push(operator);
                }
            }
        }

        while (operatorsStack.length !== 0) {
            result.push(operatorsStack.pop().symbol);
        }

        return result;
    };

    function isExpressionValid(expression) {
        return typeof (expression) === "string" && expressionValidationRegex.test(expression);
    }

    function peek(stack) {
        if (stack.length === 0) {
            return null;
        }

        return stack[stack.length - 1];
    }

    function isNumber(str) {
        return !isNaN(parseInt(str));
    }
}

var Associations = { None: '0', LeftToRight: '1', RightToLeft: '2' };

//Example of use

var operators = [
    { name: "PLUS", priority: 1, symbol: '+', association: Associations.LeftToRight },
    { name: "SUBSTRACT", priority: 1, symbol: '-', association: Associations.LeftToRight },
    { name: "MULT", priority: 2, symbol: '*', association: Associations.LeftToRight },
    { name: "DIV", priority: 2, symbol: '/', association: Associations.LeftToRight },
    { name: "DICE", priority: 3, symbol: 'd', association: Associations.LeftToRight },
    { name: "LEFT_PAR", priority: 0, symbol: '(', association: Associations.None },
    { name: "RIGHT_PAR", priority: 0, symbol: ')', association: Associations.None }
];

var infixConverter = new InfixConverter(operators);
infixConverter.toPostfix("1*(2+3d2*2)");

The big problem I have with my code is the amount of if/else if I have. My code doesn't read well but I'm having a hard time figuring out how to do better..

\$\endgroup\$
  • \$\begingroup\$ I think that all these if/else if are unavoidable. \$\endgroup\$ – Farewell Stack Exchange Aug 29 '17 at 18:51
2
\$\begingroup\$

A different approch

This answer is not intended as a better solution, just a rework to present some alternative coding methodologies to the problem.

Some refactoring.

I have done a bit of refactoring, more for my own sanity than out of sound reason and can be ignored (just can't be bothered changing them back ATM)

Symbol is a JavaScript type and using it (lower case symbol) just feels wrong so replaced it with char (for want of a better name).

Rather than instantiate the object with the object named operators I used rules. The rules get converted to operators when the object is created.

Tonkenised numbers.

One major change is that I tokenized the numbers before processing, the convert the tokens back to numbers when done. As you had it the results made it impossible to work out which numerals belong with which. Though I have not included fractions eg 0.2 that is easy to change in the regExp used to tokenize the expression.

The code.

Rather than go into detail here is the code as I have modified. I guessed at the type of input you expect, so it may well not handle some inputs. The only place I deviated from your logic is highlighted /* COULD BE A PROBLEM */

function InfixConverter(rules) {
    const expressionValidationRegex = /^([0-9]|\+|-|\(|\)|\*|\/|d)*$/;
    var operator, token = "A".charCodeAt(0);
    const tokens = {};
    const operatorsStack = []; 
    const result = [];
    const operators = {};

    function tokenize(expression){
        return expression.replace(/[0-9]+/g, (str) => {
            const nextToken = String.fromCharCode(token++);
            tokens[nextToken] = str;
            return nextToken;
        });        
    }
    function peek() { return operatorsStack[operatorsStack.length - 1]; }    
    function prepExpression(expression) {
        if (typeof expression !== "string" || ! expressionValidationRegex.test(expression)) { 
            throw new RangeError("Invalid expression."); 
        }
        result.length = operatorsStack.length = 0;
        return tokenize(expression);      
    }
    const methods = {
        rightToLeft() { operatorsStack.push(operator); },
        openBrace() { operatorsStack.push(operator); }, // this is same as above 
        leftToRight() {
            result.push(operatorsStack.pop().char);
            operatorsStack.push(operator);            
        },
        closeBrace() {
            while (peek(operatorsStack).char !== "(") { result.push(operatorsStack.pop().char); }
            operatorsStack.pop();
        }
    };
    rules.forEach(operator => {
        operators[operator.char] = operator;
        operator.move = methods[operator.move];
        operator.process = methods[operator.process];
    })
    this.toPostfix = function(expression) {
        expression = prepExpression(expression); 
        for (var i = 0; i < expression.length; i++) {
            operator = operators[expression[i]];
            if (!operator) {  
                result.push(expression[i]);
            }else{
                const precedentOperator = peek(operatorsStack);
                if (!precedentOperator) { 
                    operatorsStack.push(operator);
                } else if (operator.process) { 
                    operator.process();
                } else if (precedentOperator.process) {  /* COULD BE A PROBLEM */
                    precedentOperator.process();
                } else if (operator.priority === precedentOperator.priority) { 
                    if(operator.move) { operator.move(); }
                } else if (operator.priority > precedentOperator.priority) { 
                    operatorsStack.push(operator);
                } else if (operator.priority < precedentOperator.priority) {
                    while (operatorsStack.length !== 0 && peek(operatorsStack).priority > operator.priority) {
                        result.push(operatorsStack.pop().char); 
                    }
                    operatorsStack.push(operator);
                }
            }
        }
        while (operatorsStack.length !== 0) { result.push(operatorsStack.pop().char); }
        for (const token of Object.keys(tokens)) { result[result.indexOf(token)] = tokens[token]; }
        return result;
    };
}
const rules = [];
function addRule(char, priority, move, process) { rules.push({char, priority, move, process}); }
addRule("+", 1, "leftToRight");
addRule("-", 1, "leftToRight");
addRule("*", 2, "leftToRight");
addRule("/", 2, "leftToRight");
addRule("d", 3, "leftToRight");
addRule("(", 0, "", "openBrace");
addRule(")", 0, "", "closeBrace");
const foo = new InfixConverter(rules);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.