Problem

Write an algorithm to determine if all of the delimiters in an expression are matched and closed.

Examples

Example 1:

Input: "{ac[bb]}"
Output: true
Explanation: All delimiters are matched and closed properly.

Example 2:

Input: "[dklf(df(kl))d]{}"
Output: true
Explanation: All delimiters are matched and closed properly.

Similar Problem

Valid Parentheses

Solution

Method 1 - Using Stack

To determine if all delimiters are matched and closed, we need to use a stack data structure:

  1. Push open delimiters: Whenever we encounter an open delimiter ({, [, (), push it onto the stack.
  2. Check close delimiters: For a close delimiter (}, ], )), check if the stack is empty or if the top of the stack does not have the corresponding open delimiter. If so, the delimiters aren’t matched.
  3. Final check: After processing the entire expression, the stack should be empty. If it’s not, some open delimiters don’t have corresponding close delimiters.

Here is the approach:

  1. Initialize a stack: Create an empty stack to store open delimiters.
  2. Process the expression: Traverse characters in the expression.
    • Push open delimiters onto the stack.
    • For each close delimiter, check the stack for a matching open delimiter.
  3. Return the result: If the stack is empty after processing, all delimiters are matched.

Code

Java
class Solution {
    public boolean isValidExpression(String expression) {
        Stack<Character> stack = new Stack<>();
        for (char c : expression.toCharArray()) {
            if (c == '{' || c == '[' || c == '(') {
                stack.push(c);
            } else if (c == '}' || c == ']' || c == ')') {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if (!isMatchingPair(top, c)) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    private boolean isMatchingPair(char open, char close) {
        return (open == '{' && close == '}') ||
            (open == '[' && close == ']') ||
            (open == '(' && close == ')');
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isValidExpression("{ac[bb]}"));           // true
        System.out.println(sol.isValidExpression("[dklf(df(kl))d]{}"));  // true
        System.out.println(sol.isValidExpression("{[[[]]]}"));           // true
        System.out.println(sol.isValidExpression("{3234[fd"));           // false
        System.out.println(sol.isValidExpression("{df][d}"));            // false
    }
}
Python
class Solution:
    def isValidExpression(self, expression: str) -> bool:
        stack = []
        for char in expression:
            if char in '{[(':
                stack.append(char)
            elif char in '}])':
                if not stack:
                    return False
                top = stack.pop()
                if not self.isMatchingPair(top, char):
                    return False
        return not stack

    def isMatchingPair(self, open: str, close: str) -> bool:
        return (open == '{' and close == '}') or \
            (open == '[' and close == ']') or \
            (open == '(' and close == ')')

# Example usage
sol = Solution()
print(sol.isValidExpression("{ac[bb]}"))           # true
print(sol.isValidExpression("[dklf(df(kl))d]{}"))  # true
print(sol.isValidExpression("{[[[]]]}"))           # true
print(sol.isValidExpression("{3234[fd"))           # false
print(sol.isValidExpression("{df][d}"))            # false

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the expression because we traverse the expression once.
  • 🧺 Space complexity: O(n), in worst case when all characters are open delimiters.