prefixToPostfix.js

// An array of arguments for each case.
// Each case's arguments is also an array.
/*
let testCases = [
    ["*34".split('')],   // 34*
    ["+1*23".split('')], // 123*+
    ["+12".split('')],   // 12+
    ["+1**23/14".split('')], // 123*14/*+
]
*/

/* This is just some stuff I made so that I wouldn't have to use
 * Hackerrank's testing. Don't worry about this testing stuff.
 */
let testCases = [
    [
        [
            "*34",   // 34*
            "+1*23", // 123*+
            "+12",   // 12+
            "+1**23/14", // 123*14/*+
        ],
    ],
]

/* This is just some stuff I made so that I wouldn't have to use
 * Hackerrank's testing. Don't worry about this testing stuff.
 */
function testFunction(func, cases) {
    let caller = args => (
        { "input" : args, "output" : func.apply(null, args) }
    );
    return cases.map(caller);
}

function isOperation(string) {
    return (string === '+' ||
            string === '-' ||
            string === '*' ||
            string === '+');
}

function isNumber(string) {
    return !isNaN(string);
}


/* This is the solution that worked. Much easier.
 * - An empty token list is not valid. There has to be something.
 * - There are operators: '*', '+', '/', '-'.
 * - There are numbers, which are single digits.
 * - Every operator is binary: it has two operands. Those operands are
 *   valid prefix expressions.
 * - A valid prefix expression is either:
 *   - A number
 *   - Operator expression expression.
 * - Returns:
 *   - a tree representing the expression parsed out from the tokens
 *   - the tokens that were unparsed.
 * This actually gets a lot easier when you make the function simpler
 * and allow numbers to be valid parsable expressions.
 *
 * This function is basically a code definition of the prefix
 * expression language.
 */
function expressionToTree(tokens) {
    if (tokens.length === 0) {
        throw Error("Empty token list invalid.");
    }
    if (isNumber(tokens[0])) {
        return [tokens[0], tokens.slice(1)];
    } else {
        let leftChild, rightChild, tokensLeft;
        let operation = tokens[0];
        tokensLeft = tokens.slice(1);
        [leftChild, tokensLeft] = expressionToTree(tokensLeft);
        [rightChild, tokensLeft] = expressionToTree(tokensLeft);
        return [[operation, leftChild, rightChild], tokensLeft];
    }
}

/* It's actually a very straightforward change to turn
 * expressionToTree directly into a prefix-to-postfix converter:
 * instead of trees, return the correct postfix expression that's
 * equivalent to the prefix expression. That's what this function is,
 * the return statement for the case of operations has been modified,
 * and that's it.
 */
function prefixExpressionToPostfixExpression(tokens) {
    if (tokens.length === 0) {
        throw Error("Empty token list invalid.");
    }
    if (isNumber(tokens[0])) {
        return [tokens[0], tokens.slice(1)];
    } else {
        let leftChild, rightChild, tokensLeft;
        let operation = tokens[0];
        tokensLeft = tokens.slice(1);
        [leftChild, tokensLeft] =
            prefixExpressionToPostfixExpression(tokensLeft);
        [rightChild, tokensLeft] =
            prefixExpressionToPostfixExpression(tokensLeft);
        return [leftChild + rightChild + operation, tokensLeft];
    }
}

function prefixToPostfix(prefixes) {
    return prefixes.map(prefix => (
        prefixExpressionToPostfixExpression(prefix.split(''))[0]));
}

testFunction(prefixToPostfix, testCases).forEach((result, index) => {
    console.log(`Case ${index}:` + '-'.repeat(40));
    console.log('Input:', result.input);
    console.log('Output:', result.output)
});

/* This was my original attempt. Much more complicated and difficult,
 * and it seems this was the case because I wasn't willing to let
 * numbers be valid prefix expressions. While the question might not
 * give me a number, my code doesn't have to reflect that.
 *
 * This was an problem where the more general version was easier.
 *
function expressionToTree(tokens) {
    let operation = tokens[0];
    console.log("Original tokens:", tokens);
    console.log("Token[0]:", tokens[0]);
    console.log("Token[1]:", tokens[1]);
    console.log("Token[2]:", tokens[2]);
    console.log("Remaining Tokens:", tokens.slice(3));

    //if (tokens.length === 0) return [[], []];
    if ((isOperation(tokens[0])) && isNumber(tokens[1]) && isNumber(tokens[2])) {
        console.log("Left Child:", tokens[1]);
        console.log("Right Child:", tokens[2]);
        console.log("Remaining Tokens", tokens.slice(3));
        console.log("--------------------");
        return [[operation, tokens[1], tokens[2]], tokens.slice(3)];
    }
    else if (isOperation(tokens[0]) && isNumber(tokens[1])) {
        let leftChild, remainingTokens, rightChild;
        leftChild = tokens[1];
        remainingTokens = tokens.slice(2);
        [rightChild, remainingTokens] = expressionToTree(remainingTokens);
        console.log("Left Child:", leftChild);
        console.log("Right Child:", rightChild);
        console.log("Remaining Tokens:", remainingTokens);
        console.log("--------------------");
        return [[operation, leftChild, rightChild], remainingTokens];
    }
    else if (isOperation(tokens[0]) && isOperation(tokens[1])) {
        let leftChild, remainingTokens, rightChild;
        [leftChild, remainingTokens] = expressionToTree(tokens.slice(1));
        [rightChild, remainingTokens] = expressionToTree(remainingTokens);
        console.log("Left Child:", leftChild);
        console.log("Right Child:", rightChild);
        console.log("Remaining Tokens:", remainingTokens);
        console.log("--------------------");
        return [[operation, leftChild, rightChild], remainingTokens];
    }
}
*/