How to solve this "parse and balance angle brackets" problem? (Javascript)

Question

I am struggling with an algorithm problem I saw (and failed). Now, I am trying to understand how to solve the problem.

Question: Given a string of angle brackets, write a function that add brackets at the beginning and end of the string to make all brackets match. The angle brackets match if for every < there is a corresponding > and for every > there is a corresponding <.

The example input string : ><<><

The output string is <><<><>>

---

My main problem is how to handle multiple < characters in the input string, like <<. Based on the example given, I will end up with some nested angle brackets, but I am not currently able to figure out how to do this.

I can solve the example input, but when I give it other inputs, the output is not always what I am expecting (input #2 and input #6). Help would be appreciated.

const process = (strInput) => {

  let strOutput = [];
  let stack = [];
  let popped ='';

  for (let i = 0; i < strInput.length; i++) {

    if (strInput[i] === '>') {
      if (stack[stack.length - 1] === '<') {
        popped = stack.pop();
        strOutput.push(popped);
        strOutput.push(strInput[i]);
      } else {
        strOutput.push('<');
        strOutput.push(strInput[i]);
      }
    } else {
        if (stack[stack.length - 1] === '<') {
            strOutput.push('<');
            stack.push(strInput[i]);
        } else {
            stack.push(strInput[i]);
        }

    }   
  }

// After string has been read, check the stack for <

  for (let i = 0; i < stack.length; i++) {
    strOutput.push('>');
  }



  return strOutput.join('');
};

let result = '';

console.log('Input 1: ><<><');

result = process('><<><');

console.log('Output 1: ' + result);
console.log('Expected Output 1: ' + '<><<><>>');

console.log('Input 2: <><<');

result = process('<><<');

console.log('Output 2: ' + result);

console.log('Expected Output 2: ' + '<><<>>');

console.log('Input 3: <><<<>');

result = process('<><<<>');

console.log('Output 3: ' + result);

console.log('Expected Output 3: ' + '<><<<>>>');

console.log('Input 4: <><<<><');

result = process('<><<<><');

console.log('Output 4: ' + result);

console.log('Expected Output 4: ' + '<><<<><>>>');

console.log('Input 5: ><<>');

result = process('><<>');

console.log('Output 5: ' + result);

console.log('Expected Output 5: ' + '<><<>>');

console.log('Input 6: ><<<');

result = process('><<<');

console.log('Output 6: ' + result);

console.log('Expected Output 6: ' + '<><<<>>>');

console.log('Input 7: >>>');

result = process('>>>');

console.log('Output 7: ' + result);

console.log('Expected Output 7: ' + '<<<>>>');

Answer 1

Python Solution

import itertools



fd = "><<><"



def solution(fd):
    count = 0

    additionalLeadingOpenTags = 0
    for x in fd:
        if x == ">":

            if count ==0:
                additionalLeadingOpenTags+=1
            else:
                count -=1
        else:
            count+=1


    return ("".join(list(map(str.lower,itertools.repeat("<", additionalLeadingOpenTags)))) + fd +"".join(list(map(str.lower,itertools.repeat(">", count)))))

Answer 2

Java Version

public static void main(String[] args) {

    String s = "><<><";

    int openCount = 0;
    int additionalLeadingOpenTags = 0;

    for (char c : s.toCharArray()) {
        if (c == '>') {
            if (openCount == 0) {
                additionalLeadingOpenTags++;
            } else {
                openCount--;
            }
        } else {
            openCount++;
        }
    }

    StringBuilder result = new StringBuilder();
    while (additionalLeadingOpenTags > 0) {
        result.append("<");
        additionalLeadingOpenTags--;
    }
    result.append(s);
    while (openCount > 0) {
        result.append(">");
        openCount--;
    }

    System.out.println(result.toString());
}

Answer 3

Swift Version

Helps for reference

//  Input: "><<><"
//  Output: "<><<><>>"

class Angles {

func addAngles(angles: String) -> String {

var openingCount = 0
var leadingOpenCounts = 0
var newAngles = ""

newAngles = angles

print("New angles \(newAngles)")

for c in newAngles {


    print("Char = \(String(c) )")

    if String(c) == ">" {

        if openingCount == 0 {
            leadingOpenCounts = leadingOpenCounts + 1
        }
        else {
            openingCount = openingCount - 1
        }

    }
    if String(c) == "<" {
        openingCount = openingCount + 1
    }

}

print("LeadingOpenCounts ***** = \(leadingOpenCounts)")
print("OpeningCount ***** = \(openingCount)")
print("Required Closing Count ***** = \(openingCount)")

for _ in 0..<leadingOpenCounts {

    newAngles = "<" + newAngles
}

for _ in 0..<openingCount {
    newAngles.append(">")
}

print(newAngles)
return newAngles
}

}

let angles = Angles()
//><<><
// ><<<>>>
angles.addAngles(angles: "><<><")

Answer 4

To simplify things, rather than using a stack array, consider using just a single number: the number of open < tags so far. When a > is encountered, if there are no current open tags, add a < to the beginning of the string (while keeping the open tag count at 0). Then, at the end, add a number of >s matching the number of currently open tags:

const process = (str) => {
  let openCount = 0;
  let additionalLeadingOpenTags = 0;
  for (const char of str) {
    if (char === '>') {
      if (openCount === 0) {
        additionalLeadingOpenTags++;
      } else {
        openCount--;
      }
    } else {
      openCount++;
    }
  }
  return '<'.repeat(additionalLeadingOpenTags) + str + '>'.repeat(openCount);
};

console.log('Input 1: ><<><');

result = process('><<><');

console.log('Output 1: ' + result);
console.log('Expected Output 1: ' + '<><<><>>');

console.log('Input 2: <><<');

result = process('<><<');

console.log('Output 2: ' + result);

console.log('Expected Output 2: ' + '<><<>>');

console.log('Input 3: <><<<>');

result = process('<><<<>');

console.log('Output 3: ' + result);

console.log('Expected Output 3: ' + '<><<<>>>');

console.log('Input 4: <><<<><');

result = process('<><<<><');

console.log('Output 4: ' + result);

console.log('Expected Output 4: ' + '<><<<><>>>');

console.log('Input 5: ><<>');

result = process('><<>');

console.log('Output 5: ' + result);

console.log('Expected Output 5: ' + '<><<>>');

console.log('Input 6: ><<<');

result = process('><<<');

console.log('Output 6: ' + result);

console.log('Expected Output 6: ' + '<><<<>>>');