Need to Check That Braces in Given Array Are Balanced or Not

Need to check that braces in given array are balanced or not

import Foundation

extension String {

    func isBalanced() -> Bool {
        switch self.filter("()[]{}".contains)
            .replacingOccurrences(of: "()", with: "")
            .replacingOccurrences(of: "[]", with: "")
            .replacingOccurrences(of: "{}", with: "") {
        case "": return true
        case self: return false
        case let next: return next.isBalanced()
        }
    }

}

To explain:

1. filter("()[]{}".contains) removes any characters except the delimiters. It means the same as filter({ c in "()[]{}".contains(c) }).

2. Any finite-length, non-empty balanced string must contain one or more empty delimiter pairs ((), [], or {}). Deleting all empty pairs doesn't change the balanced-ness of the string. So delete any such empty pairs using replacingOccurrences(of:with:).

3. If, after deleting all empty pairs, you have an empty string, then you started with a balanced string, so return true.

4. If, after deleting all empty pairs, you didn't actually remove any empty pairs (and you don't have an empty string), then you must have an unbalanced delimiter, so return false.

5. If, after deleting all empty pairs, you removed at least one pair, then you might now have new empty pairs. For example, deleting the empty pairs of [({})][({})] gives [()][()], which has new empty pairs. So try to do more deleting by calling isBalanced tail-recursively.

My code only works if blocks are in a certain order

Your outermost for block increments index i but the code inside removes elements from the array. So if the inner code removes anything from the array, when the outer loop is run again, it skips the new first element.

{}()[]

first run of outer loop removes {} and []

now stringArray is ()

second run of outer loop now starts at index 1, which is ), so it doesn't find the pair.

Wrote a C++ code to check if expression has balanced parenthesis and my code is not running. I have been stuck for a day now

You have 2 bugs. The first is reading your input string into your stack, this will at minimum get very confusing and at worst not work.

The second is that when checking for matching tags you check that the opening bracket is the same as the closing one, this will never be true, you need to check that the opening bracket is the same type as the closing one.

One way of solving both bugs would be:

int main()
{
    // match variable to keep track that closing bracket and opening brackets are in sequence
    char match = '\0';
    bool isMatching = true;
    // resetting the stack variables and attributes
    stack.top = -1;
    stack.array = new char[1000];
    std::string input;
    cout << "Enter the Expression to match the parenthesis: ";
    cin >> input;

    std::map<char, char> opening = { { ')', '(' }, { '}', '{' }, { ']', '[' } };

    // traversing through the character array and matching parenthesis
    for (char ch : input)
    {
        // if character is an opening bracket
        if (ch == '(' || ch == '{' || ch == '[')
            push(ch);
        // if character is a closing bracket
        else if (ch == ')' || ch == '}' || ch == ']')
        {
            match = pop();
            auto open = opening.find(ch);
            if (open == opening.end() || open->second != match )
                isMatching = false;
        }
    }
    if (isMatching == true)
        cout << "Parenthesis Matched" << endl;
    else
        cout << "Not matched" << endl;
    delete[] stack.array;
    return 0;
}

Program to balance the braces

Follow the below algo:

1) Use a stack

2) read string from left

3) push to stack if current read letter is open brace ('(','{','[')

4) pop from stack if current read letter is close brace.

5) Check the popped brace with the current read brace

5.a) if it is pairing brace. ok continue

5.b) if stack was empty, then print NO

5.c) if popped char and read char is not a pair then print NO

6) when all the string are processed. check the length of the stack.

6.a) if length is 0 print YES

6.b) else print NO

Check if the input string consisting of braces is well-formed

There are multiple problems in your code:

• you call cross(str, str[i], str[j]); instead of cross(str, i, j); when you find matches for parentheses and brackets.
• the break statement should be moved inside the if block.
• your method does not allow detection of nesting errors
• your method would have undefined behavior if str is an empty string (which you cannot input via scanf())

Here is a modified version:

#include <stdio.h>

void cross(char str[], int i, int j) {
    str[i] = str[j] = 'X';
}

int iscrossed(char str[]) { 
    int i = 0;
    while (str[i] != '\0') {
        if (str[i] != 'X')
            return 0;
        i++;
    }
    return 1;
}

int check(char str[]) {
    int i = 0, j;
    while (str[i] != '\0') {
        if (str[i] == ')') {
            for (j = i - 1; j >= 0; j--) {
                if (str[j] == '(') {
                    cross(str, i, j);
                    break;
                }
            }
        } else
        if (str[i] == ']') {
            for (j = i - 1; j >= 0; j--) {
                if (str[j] == '[') {
                    cross(str, i, j);
                    break;
                }
            }
        }
        i++;
    }
    return iscrossed(str);
}

int main() {
    char str[80];
    if (scanf("%79s", str) == 1) {
        printf("%d\n", check(str));
    }
    return 0;
}

Here is a simpler alternative:

#include <stdio.h>

const char *check(const char str[], int endc) {
    while (str) {
        int c = *str++;
        switch (c) {
          case '(': str = check(str, ')'); break;
          case '[': str = check(str, ']'); break;
          case '{': str = check(str, '}'); break;
          case ')':
          case ']':
          case '}':
          case '\0': return c == endc ? str : NULL;
        }
    }
    return NULL;
}

int main() {
    char str[80];
    if (fgets(str, sizeof str, stdin)) {
        printf("%d\n", check(str, '\0') != NULL);
    }
    return 0;
}

Check if a given string is balanced brackets string, recursively

The idea is to keep a list of the opened brackets, and if you find a closing brackt, check if it closes the last opened:

• If those brackets match, then remove the last opened from the list of openedBrackets and continue to check recursively on the rest of the string
• Else you have found a brackets that close a nerver opened once, so it is not balanced.

When the string is finally empty, if the list of brackes is empty too (so all the brackes has been closed) return true, else false

ALGORITHM (in Java):

public static boolean isBalanced(final String str1, final LinkedList<Character> openedBrackets, final Map<Character, Character> closeToOpen) {
    if ((str1 == null) || str1.isEmpty()) {
        return openedBrackets.isEmpty();
    } else if (closeToOpen.containsValue(str1.charAt(0))) {
        openedBrackets.add(str1.charAt(0));
        return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
    } else if (closeToOpen.containsKey(str1.charAt(0))) {
        if (openedBrackets.getLast() == closeToOpen.get(str1.charAt(0))) {
            openedBrackets.removeLast();
            return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
        } else {
            return false;
        }
    } else {
        return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
    }
}

TEST:

public static void main(final String[] args) {
    final Map<Character, Character> closeToOpen = new HashMap<Character, Character>();
    closeToOpen.put('}', '{');
    closeToOpen.put(']', '[');
    closeToOpen.put(')', '(');
    closeToOpen.put('>', '<');

    final String[] testSet = new String[] { "abcdefksdhgs", "[{aaa<bb>dd}]<232>", "[ff{<gg}]<ttt>", "{<}>" };
    for (final String test : testSet) {
        System.out.println(test + "  ->  " + isBalanced(test, new LinkedList<Character>(), closeToOpen));
    }
}

OUTPUT:

abcdefksdhgs  ->  true
[{aaa<bb>dd}]<232>  ->  true
[ff{<gg}]<ttt>  ->  false
{<}>  ->  false

Note that i have imported the following classes:

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

---

Related Topics