Simple parenthesis removal - JavaScript

Question

I solved the following problem:

You will be given a mathematical string and your task will be to remove all braces as follows:

solve("x-(y+z)") = "x-y-z"`

solve("x-(y-z)") = "x-y+z"`

solve("u-(v-w-(x+y))-z") = "u-v+w+x+y-z"`

solve("x-(-y-z)") = "x+y+z"`

There are no spaces in the expression. Only two operators are given: "+" or "-".

This is the solution I came up with:

function removeAt(s, index) {
    if (index === s.length - 1) {
        return s.slice(0, -1)
    }
    return s.slice(0, index) + s.slice(index + 1);
}

function insertAt(s, index, str) {
    return s.slice(0, index) + str + s.slice(index);
}

function replaceAt(s, index, chr) {
    if (index > s.length - 1) return s;
    return s.slice(0, index) + chr + s.slice(index + 1);
}

function reverseSigns(s, start, end) {
    for (var i = start; i < end; i++) {
        if (s[i] === '-') {
            s = replaceAt(s, i, '+');
        } else if (s[i] === '+') {
            s = replaceAt(s, i, '-');
        }
    }
    return s;
}

function solve(s) {
    //Get the position of the parenthesis 
    var Close = 0, Open = -1;
    while (s[Close] !== ')' && Close < s.length) {
        if (s[Close] === '(') {
            Open = Close;
        }
        Close++;
    }
    //Check to see if there is any parenthesis 
    if (Open !== -1) {
        //Insert sign before if there is none
        if (s[Open + 1] !== '+' && s[Open + 1] !== '-') {
            s = insertAt(s, Open + 1, '+');
            //'Close' parenthesis has changed --> +1 right
            Close++;
        }
        //Check to see if a sign has to be replaced 
        if (s[Open - 1] === '-') {
            s = reverseSigns(s, Open + 1, Close - 1);
        }
        //Remove the parenthesis 
        s = removeAt(s, Close);
        s = removeAt(s, Open);
        //Remove the sign before paranthesis
        if (s[Open - 1] === '-' || s[Open - 1] === '+') {
            s = removeAt(s, Open - 1);
        }
        //Recursive call
        return solve(s);
        //return s;
    }
    //Remove unnecessary +
    if (s[0] === '+') {
        s = removeAt(s, 0);
    }
    return s;
}

I was wondering if my code could be improved.

Answer 1

Recursion, AST's, and encapsulation.

The lesson of this problem is Abstract Syntax Trees (AST).

To parse from human readable syntax to an abstract tree, then use that tree to transform the code back to a human readable string.

What you have created is a string butcher that slices a string to bits, beats them into shape and throws the remains onto a plate. (Sorry but your solution is very inelegant)

Style note

In ECMAScript the convention is that capitals only for functions invoked with the new token.

Encapsulate functions

When you create solutions that rely on a set of function specific to the task it is best to encapsulate the functions within the main function.

For example

function foo() {...}
function bar() {...}
function solve() {
    foo();
    bar();
}

Is better as

function solve() {
    function foo() {...}
    function bar() {...}
    foo();
    bar();
}

Though if you are recusing the solve function you need to avoid encapsulating inside the recursion as this will create additional and unneeded closures. So for recursion you would do the following to encapsulate your state functions:

function solve(args) {
    function foo() {...}
    function bar() {...}
    return (function solve() {            
        if(foo()) { return solve() };
        return bar();
    })(args);
}

AST

Your solution is too complex.

What struck me when I first looked at the code is all the offset variables (s[Open + 1] !== '+' && s[Open + 1] !== '-') In your code I counted 13 times you add 1 to or subtract 1 from a variable.

The root cause it that you are using the input string to store the partial solution, which means that as you scan the string you need to constantly re-position your scan position, resulting in the messy offsets all over the place.

When you need to parse a nested token string you avoid modifying the string. You scan the string one token at a time, as you do you convert each token "(", ")", "+", "-", and /[a-z]/ to a more convenient abstract form.

In computer science these are usually called AST and represent the input string in a machine readable form, rather than the human readable form that the input string is in.

Stacks and Recursion

Recursion in ECMAScript its unfortunately flawed. For most cases it is generally safe, but you are always at risk of call stack overflow. You can not know how deep you are in the call stack when the function is first called so you can never be sure that there is room to complete the iteration.

As most recursive functions are just state stacks you can write an alternative solution without recursion and using an array as a stack. This offers many advantages:

1. Only relevant state is pushed to the stack
2. You have a much deeper iteration level
3. Improved performance and memory use.

A rewrite

This is a non-recursive, imperative , partial AST parser, and transformer.

The recursive stack is implemented as an array with push and pop methods replacing recursive call and exits respectively.

It is imperative as it uses an encapsulated state to communicate between its parts. Note how most functions do not have arguments or return values. The data they need to fulfill their role is in the common shared state, i, node, sign, stack and equ. This reduces source code noise and improves execution efficiency.

It is a Partial AST parser / transformer because it consumes the child nodes as it parses the input string. This is because the AST is not needed and there is a performance gain by dumping the unneeded parts of the AST as we go.

It is assumed that all input is correctly formed containing no errors.

function solve(equ) {
    var node, sign = 1, i = 0;
    const stack = [];
    function push() {
        if (node) { stack.push(node) }
        node= {sign, vars : []};
        sign = 1;
    }
    function variable(id = equ[i]) {
        node.vars.push({sign, id});
        sign = 1;
    }    
    function pop() {
        const child = node;
        node = stack.pop();
        for (const v of child.vars) {
            sign = v.sign * child.sign;
            variable(v.id);
        }
    }
    function result(str = "") {
        for (const v of node.vars) { str += ((v.sign * node.sign) < 0 ? "-" : "+") + v.id }
        return str[0] === "+" ? str.substr(1) : str;
    }       
    push();  
    while(i < equ.length){
        if (equ[i] === "(") { push() }
        else if (equ[i] === ")") { pop() }
        else if (equ[i] === "+") { sign *= 1 }
        else if (equ[i] === "-") { sign *= -1 }
        else { variable() }
        i++;    
    }
    return result();
}

Answer 2

I would do this by iterating through the tokens and keeping a stack of the current state (signStack) as parenthesis are opened.

function newSign(current, prev) {
  //treat blank as positive
  const currentNegative = current[0] == '-';
  const prevNegative    = prev[0]    == '-';
  return currentNegative == prevNegative ? '+' : '-';
}

function solve(input) {
  let signStack   = ['+']; // start by assuming positive
  let currentSign = '';
  
  const result = input.replace(/(\+|\-)\(?|\)|\w/g, (match) => {
    if (match==')') { // close parenthesis
      signStack.shift(); 
      currentSign = signStack[0];
      return '';
    } 
    
    if (match[0] != '+' && match[0] != '-') { // variable
      const  sign = currentSign;
      currentSign = signStack[0];;
      return sign + match;
    }
    
    const sign     = newSign(match, currentSign);
    currentSign    = sign;
    if (match.length > 1) {// open parenthesis
      signStack.unshift(sign);
    }
    return '';
  });  
  
  if (signStack.length != 1)
    throw 'unbalanced parenthesis';
    
  return result;  
}

function test(input, expected) {
  const result = solve(input);
  if (result != expected)
    console.log(`Failed: input=${input}, result=${result}, expected=${expected}`); 
}

test("x-(y+z)",        "x-y-z");
test("x-(y-z)",        "x-y+z");
test("u-(v-w-(x+y))-z", "u-v+w+x+y-z");
test("x-(-y-z)",        "x+y+z");

Answer 3

1. Use proper naming conventions: Open and Close should be lowercase.
2. I'm slightly confused what Open and Close are supposed to do.
3. Why do you need recursion instead of a loop?