Wednesday, March 7, 2018

Parentheses Expression Parser

Overview 


A simple coding exercise, parsing parentheses expressions
  • Given a string containing the characters '(', ')', '{', '}', '[' and ']' and any other characters in between determine if the parentheses are balanced.
using mocha+chai test framework.

Valid Expressions

 - "()"
 - "(){}[]"
 - "([ok])"
 - "{([ok])}"
 - "function() { return (1+1); }"

Invalid Expressions

 - "(]"
 - "([)]"
 - "([ok]})"
 - "{([ok])})"

Github Repo: ParenthesesParser

Source Code

let Stack = require('./Stack');
let print = console.log;

function ParenthesesParser(expression) {

    this._parentheseDefinition = {
        '(' : ')', 
        '{' : '}', 
        '[' : ']',
    };
    this.parse = function(expression) {

        if(!expression)
            throw new Error(ParenthesesParser.EXPRESSION_CANNOT_BE_NULL_OR_UNDEFINED);

        let stack = new Stack();

        for(let i = 0; i < expression.length; i++) {
            let c = expression.charAt(i);
            if(this.isOpenParenthese(c)) {
                stack.push(c);
            }
            else {
                if(this.isCloseParenthese(c)) {
                    let p = stack.pop();
                    if(c !== this._parentheseDefinition[p]) // Fail
                        return this.createResult(false, `position:${i}, expected:${this._parentheseDefinition[p]}, found:${c}`);
                }
            }
        }
        // if stack is empty the expression is valid else we have an invalid expression
        // with a missing closing parenthese like this '(ok'
        const passed = stack.isEmpty();
        return this.createResult(passed, passed ? `` : `expected:"${this._parentheseDefinition[stack.pop()]}" at end of expression`);
    }
    this.createResult = function (passed, errorMsg) {
        return {
            Expression   : this._expression,
            Passed       : passed,
            ErrorMessage : ParenthesesParser.PARSING_ERROR + " " + errorMsg
        };
    }
    this.isOpenParenthese = function(c) {

        return c in this._parentheseDefinition;
    }
    this.isCloseParenthese = function(c) {
        
        return Object.values(this._parentheseDefinition).indexOf(c) !== -1;
    }
};

ParenthesesParser.EXPRESSION_CANNOT_BE_NULL_OR_UNDEFINED = "expression cannot be null or undefined";
ParenthesesParser.PARSING_ERROR                          = "Parsing Error";

module.exports = ParenthesesParser;


Unit tests


let assert = require('chai').assert;
let expect = require('chai').expect;
let ParenthesesParser = require('../src/ParenthesesParser');
let print = console.log;

describe('ParenthesesParser', () => {

    let subject;

    before(() => {
        subject = new ParenthesesParser();
    });
    
    describe('Valid expressions', () => {

        let validExpressions = [
            "()" ,"(a)", "((((()))))", 
            "((((([[[]]])))))",  "((((([[[{{{}}}]]])))))",  "((((([[[{{{a}}}]]])))))", 
            "function(abs(compute(run(exec(array[list[array[object{object{object[1]}}]]])))))", 
            "(){}[]" , "(()){{}}[[]]" ,
            "([ok])" ,
            "{([ok])}" ,
            "function() { return (1+1); }" ,
            "<(>)", // This one passed because '<' and '>' are not considered Parentheses
            "(\\)", "(\\//)", "(\")",
            "Valid-Expression", "(Valid-Expression)"
        ];
        it(`should return passed on expression '${validExpressions}'`, () => {

            validExpressions.forEach((exp) =>{
                expect(subject.parse(exp).Passed).to.be.true;
            });
        });
    });

    describe('Invalid expressions', () => {
       
        let invalidExpressions = [
            "(invalid-expression", "invalid-expression)",
            "(" , "((((())))", , "(((((])))))", 
            "[", "{",
            "(){[]" ,
            "([ok)" ,
            "{([ok]}" ,
            "function() { return (1+1; }" ,
        ];
        it(`should return failed on expression '${invalidExpressions}'`, () => {

            invalidExpressions.forEach((exp) =>{
                expect(subject.parse(exp).Passed).to.be.false;
            });
        });
        it(`should return specific error message on failure`, () => {

            let exp = "[(a])";
            let expected = "Parsing Error position:3, expected:), found:]";
            let result = subject.parse(exp);
            expect(result.ErrorMessage).to.equal(expected);
            expect(result.ErrorMessage.startsWith(ParenthesesParser.PARSING_ERROR)).to.be.true;
        });
        it(`should return specific error message on failure, complex expression`, () => {

            let exp = "((((([[[{{{a)}}}]]])))))";
            let expected = "Parsing Error position:12, expected:}, found:)";
            let result = subject.parse(exp);
            expect(result.ErrorMessage).to.equal(expected);
        });
    });

    describe('Invalid expressions, missing closing parenthese', () => {

        it(`should return specific error message on failure on '(ok'`, () => {

            let exp = "(ok";
            let expected = 'Parsing Error expected:")" at end of expression';
            let result = subject.parse(exp);
            expect(result.ErrorMessage).to.equal(expected);
        });

        let invalidExpressionsMissingClosingParentheses = [
            "(ok", "{ok", "[ok",
        ];
        it(`should return error message on failure ${invalidExpressionsMissingClosingParentheses}`, () => {

            invalidExpressionsMissingClosingParentheses.forEach((exp) => {

                let result = subject.parse(exp);
                expect(result.ErrorMessage.startsWith(ParenthesesParser.PARSING_ERROR)).to.be.true;
            });
        });
    });

    describe('Invalid parameters', () => {

        it(`should throw exception on empty string`, () => {
            expect(function () { subject.parse("");}).to.throw(ParenthesesParser.EXPRESSION_CANNOT_BE_NULL_OR_UNDEFINED);
        });
        it(`should throw exception on null string`, () => {
            expect(function () { subject.parse(null);}).to.throw(ParenthesesParser.EXPRESSION_CANNOT_BE_NULL_OR_UNDEFINED);
        });
        it(`should throw exception on undefined string`, () => {
            expect(function () { subject.parse(undefined);}).to.throw(ParenthesesParser.EXPRESSION_CANNOT_BE_NULL_OR_UNDEFINED);
        });
    });

    describe('Utility methods', () => {

        it(`isOpenParenthese() positive cases`, () => {
            ['(', "{", "["].forEach((c) => {
                expect(subject.isOpenParenthese(c)).to.be.true;
            });
        });
        it(`isOpenParenthese() negative cases`, () => {
            ['a', "b", "c"].forEach((c) => {
                expect(subject.isOpenParenthese(c)).to.be.false;
            });
        });
        it(`isCloseParenthese() positive cases`, () => {
            [')', "}", "]"].forEach((c) => {
                expect(subject.isCloseParenthese(c)).to.be.true;
            });
        });
        it(`isCloseParenthese() negative cases`, () => {
            ['a', "b", "c"].forEach((c) => {
                expect(subject.isCloseParenthese(c)).to.be.false;
            });
        });
    });
});


No comments:

Post a Comment