Skip to main content

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

Popular posts from this blog

UILabel text animation as in UIButton click

Animating UILabel textcolor is not easy as it seems, normal animation won't work on this property. The below code snippet animates the UILabel textcolor as in button click.
Change the duration and UIViewAnimationOptions to play with it. extensionUILabel{ func flashLabel() { func animate(duration:Double,alpha:CGFloat,completion:(()->())?){ UIView.transition(with: self, duration: duration, options: UIViewAnimationOptions.transitionCrossDissolve, animations: { self.textColor = self.textColor?.withAlphaComponent(alpha) }) { _ in completion?() } } animate(duration: 0.1, alpha: 0) { animate(duration: 0.3, alpha: 1, completion: nil) } } } Happy coding...

Confused OS Concepts

Difference between MultiProcessor and Multicore Processor? A multiprocessorsystem contains more than one CPU, allowing them to work in parallel.
multicoreCPU has multiple execution cores on one CPU so that multiple cores can work in parallel on separate operations at chip level. Difference between MultiProgramming, MultiTasking, MultiProcessing,      MultiThreading? MultiProgramming:To minimize the CPU Idle time, Multiprogramming was introduced in older days for single core processor. One or more programs are loaded into main memory which are ready to execute still, only one program is able to get the CPU for execution while all others are waiting for their turn. When currently running process is performing an I/O task, then OS may interrupt that process and give the control to another program(process context switching) loaded in main memory for execution and a running process keeps executing until either it voluntarily releases the CPU or when it blocks for an I/O operation.
With Mutil…