Stack Problem - Balancing of Symbols
In case if you are wondering, how to implement a STACK, Please click here.
Problem:
Given an expression string exp , write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp.
Example:
Algorithm:
Input: exp = “[()]{}{[()()]()}”
Output: Balanced
Output: Balanced
Input: exp = “[(])”
Output: Not Balanced
Output: Not Balanced
- 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.
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