Skip to main content

Posts

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 > 0else { return false } let symbols:[Character:Character] = ["{":"}","[":"]","(":")",] v…

Stacks

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 symbolsInfix-to-Postfix conversionEvaluation of postfix expressionImplementing 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 operations
Top: Returns the last element without removing…