Skip to main content


Showing posts from December, 2019

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 ] = [ "{" : "}&qu


What is a Stack ? A Stack ADT is an ordered list in which insertion and deletion are done at the top end of the list. A stack follows LIFO(Last In First Out) Principle i.e, the last element inserted is the first one to be deleted. Why do we need Stack? Well, in many algorithms you want to add objects to a temporary list at some point and then pull them off this list again at a later time. Often the order in which you add and remove these objects matters. Applications of Stack Balancing of symbols Infix-to-Postfix conversion Evaluation of postfix expression Implementing function calls(Recursive) Forward and Backward feature in a browser. Redo & Undo sequence in a text editor. Matching tags in HTML & XML. Used in other algorithms like Tree traversal, Tower of Hanoi, Stock span, N Queens, etc. Stack Operations Main stack operations Push : Inserts data onto stack Pop : Removes and returns the last inserted element from the stack. Auxiliary stack operation