Stack Problem - Balancing of Symbols

Stack Problem - Balancing of Symbols
Problem:
Given an expression string exp , write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp.

Example:
Input: exp = “[()]{}{[()()]()}”
Output: Balanced
Input: exp = “[(])”
Output: Not Balanced

Algorithm:
  • Create a stack.
  • while ( end of input is not reached ) {
    • If the character read is not a symbol to be balanced, ignore it.
    • If the character is an opening delimiter like ( , {  or [ , PUSH it into the stack.
    • If it is a closing symbol like ) , } , ] , then if the stack is empty report an error, otherwise POP the stack.
    • If the symbol POP-ed is not the corresponding delimiter, report an error.
  • At the end of the input, if the stack is not empty report an error.
Implementation :
func balancingOfSymbols(string:String)->Bool{
        guard string.count > 0 else { return false }
        let symbols:[Character:Character] = ["{":"}","[":"]","(":")",]
        var symbolStack:Stack<Character> = Stack()
        var isBalanced = true
        
        for char in string  {
            if symbols.keys.contains(char){
                symbolStack.push(char)
            }else if symbols.values.contains(char){
                if let poppedSymbol = symbolStack.pop(), symbols[poppedSymbol] == char{
                    continue
                }else{
                     isBalanced = false
                    break
                }
            }
        }
        isBalanced = isBalanced ? symbolStack.count == 0 : isBalanced
        return isBalanced
    }
Time Complexity: O(n)

In case if you are wondering, how to implement a STACK, Please click here.

Comments

Post a Comment

Popular posts from this blog

Swift Package Manager: Demystifying Targets and Libraries

Target vs Library If you'v dabbled with Swift Package Manager (SwiftPM), you've likely encountered targets and libraries in a Package.swift file and wondered what sets them apart. These concepts are essential to structuring your code effectively, especially as projects grow larger. In this post, we'll break down the difference between the two, explore how they're used, and walk through real-world examples that show how you can build scalable and modular Swift packages. What Exactly Is a Target? In SwiftPM, a target is the fundamental unit of code compilation. It's basically a module that consists of source files, dependencies, and optionally resources or tests. Targets are used internally within your package. For example: .target(name: "Logger") This line defines a module named Logger . You can import and use this module from other targets inside your package. And a Library? A library is a product. It’s what you offer to the outside world—other packag...
Read more

IOS Simulator Crash report

If your iOS app crashes in the Simulator during a test run, the crash report can be used for diagnosing the exact cause of the crash. By default, the crash reports for the app will be written to the ~/Library/Logs/DiagnosticReports directory. The crash reports can be uploaded as artifacts to assist with debugging the app crash on your local machine: - store_artifacts: path: ~/Library/Logs/DiagnosticReports
Read more

Palindrome check

A Palindrome is a word, phrase, or sequence that reads the same backward as forward. Ex: RaceCar, madam, mom, level We have two methods to check for a palindrome. 1. Reverse String Comparision: If we reverse a string and compare it with the given string, then if both the strings are equal, we can say the given string is a palindrome. func reversedString(input: String )-> String { var reversed = "" for char in input{ reversed = "\(char)" + reversed } return reversed } func isPalindrome( _ input : String )-> Bool { let reversed = reversedString (input: input) return reversed == input } Time Complexity: θ(n) Space Complexity: θ(n) 2. Character Comparision: We'll start comparing the first character with the last character, if both are equal we'll increment the left index & decrement the right index until we cross the middle character. If we successfully pass the middle character then the given s...
Read more