An encoded string (s) is given, the task is to decode it. The pattern in which the strings are encoded is as follows.
<count>[sub_str] ==> The substring 'sub_str' appears count times.
Examples:
Input : str[] = "1[b]" Output : b Input : str[] = "2[ab]" Output : abab Input : str[] = "2[a2[b]]" Output : abbabb Input : str[] = "3[b2[ca]]" Output : bcacabcacabcaca
The idea is to use two stacks, one for integers and another for characters.
Now, traverse the string,
- Whenever we encounter any number, push it into the integer stack and in case of any alphabet (a to z) or open bracket (‘[‘), push it onto the character stack.
- Whenever any close bracket (‘]’) is encounter pop the character from the character stack until open bracket (‘[‘) is not found in the character stack. Also, pop the top element from the integer stack, say n. Now make a string repeating the popped character n number of time. Now, push all character of the string in the stack.
Below is implementation of this approach:
C++
// C++ program to decode a string recursively // encoded as count followed substring #include<bits/stdc++.h> using namespace std; // Returns decoded string for 'str' string decode(string str) { stack< int > integerstack; stack< char > stringstack; string temp = "" , result = "" ; // Traversing the string for ( int i = 0; i < str.length(); i++) { int count = 0; // If number, convert it into number // and push it into integerstack. if (str[i] >= '0' && str[i] <= '9' ) { while (str[i] >= '0' && str[i] <= '9' ) { count = count * 10 + str[i] - '0' ; i++; } i--; integerstack.push(count); } // If closing bracket ']', pop elemment until // '[' opening bracket is not found in the // character stack. else if (str[i] == ']' ) { temp = "" ; count = 0; if (! integerstack.empty()) { count = integerstack.top(); integerstack.pop(); } while (! stringstack.empty() && stringstack.top()!= '[' ) { temp = stringstack.top() + temp; stringstack.pop(); } if (! stringstack.empty() && stringstack.top() == '[' ) stringstack.pop(); // Repeating the popped string 'temo' count // number of times. for ( int j = 0; j < count; j++) result = result + temp; // Push it in the character stack. for ( int j = 0; j < result.length(); j++) stringstack.push(result[j]); result = "" ; } // If '[' opening bracket, push it into character stack. else if (str[i] == '[' ) { if (str[i-1] >= '0' && str[i-1] <= '9' ) stringstack.push(str[i]); else { stringstack.push(str[i]); integerstack.push(1); } } else stringstack.push(str[i]); } // Pop all the elmenet, make a string and return. while (! stringstack.empty()) { result = stringstack.top() + result; stringstack.pop(); } return result; } // Driven Program int main() { string str = "3[b2[ca]]" ; cout << decode(str) << endl; return 0; } |
Java
// Java program to decode a string recursively // encoded as count followed substring import java.util.Stack; class Test { // Returns decoded string for 'str' static String decode(String str) { Stack<Integer> integerstack = new Stack<>(); Stack<Character> stringstack = new Stack<>(); String temp = "" , result = "" ; // Traversing the string for ( int i = 0 ; i < str.length(); i++) { int count = 0 ; // If number, convert it into number // and push it into integerstack. if (Character.isDigit(str.charAt(i))) { while (Character.isDigit(str.charAt(i))) { count = count * 10 + str.charAt(i) - '0' ; i++; } i--; integerstack.push(count); } // If closing bracket ']', pop elemment until // '[' opening bracket is not found in the // character stack. else if (str.charAt(i) == ']' ) { temp = "" ; count = 0 ; if (!integerstack.isEmpty()) { count = integerstack.peek(); integerstack.pop(); } while (!stringstack.isEmpty() && stringstack.peek()!= '[' ) { temp = stringstack.peek() + temp; stringstack.pop(); } if (!stringstack.empty() && stringstack.peek() == '[' ) stringstack.pop(); // Repeating the popped string 'temo' count // number of times. for ( int j = 0 ; j < count; j++) result = result + temp; // Push it in the character stack. for ( int j = 0 ; j < result.length(); j++) stringstack.push(result.charAt(j)); result = "" ; } // If '[' opening bracket, push it into character stack. else if (str.charAt(i) == '[' ) { if (Character.isDigit(str.charAt(i- 1 ))) stringstack.push(str.charAt(i)); else { stringstack.push(str.charAt(i)); integerstack.push( 1 ); } } else stringstack.push(str.charAt(i)); } // Pop all the elmenet, make a string and return. while (!stringstack.isEmpty()) { result = stringstack.peek() + result; stringstack.pop(); } return result; } // Driver method public static void main(String args[]) { String str = "3[b2[ca]]" ; System.out.println(decode(str)); } } |
Python3
# Python program to decode a string recursively # encoded as count followed substring # Returns decoded string for 'str' def decode( Str ): integerstack = [] stringstack = [] temp = "" result = "" # Traversing the string for i in range ( len ( Str )): count = 0 # If number, convert it into number # and push it into integerstack. if ( Str [i] > = '0' and Str [i] < = '9' ): while ( Str [i] > = '0' and Str [i] < = '9' ): count = count * 10 + ord ( Str [i]) - ord ( '0' ) i + = 1 i - = 1 integerstack.append(count) # If closing bracket ']', pop elemment until # '[' opening bracket is not found in the # character stack. elif ( Str [i] = = ']' ): temp = "" count = 0 if ( len (integerstack) ! = 0 ): count = integerstack[ - 1 ] integerstack.pop() while ( len (stringstack) ! = 0 and stringstack[ - 1 ] ! = '[' ): temp = stringstack[ - 1 ] + temp stringstack.pop() if ( len (stringstack) ! = 0 and stringstack[ - 1 ] = = '[' ): stringstack.pop() # Repeating the popped string 'temo' count # number of times. for j in range (count): result = result + temp # Push it in the character stack. for j in range ( len (result)): stringstack.append(result[j]) result = "" # If '[' opening bracket, push it into character stack. elif ( Str [i] = = '[' ): if ( Str [i - 1 ] > = '0' and Str [i - 1 ] < = '9' ): stringstack.append( Str [i]) else : stringstack.append( Str [i]) integerstack.append( 1 ) else : stringstack.append( Str [i]) # Pop all the elmenet, make a string and return. while len (stringstack) ! = 0 : result = stringstack[ - 1 ] + result stringstack.pop() return result # Driven code if __name__ = = '__main__' : Str = "3[b2[ca]]" print (decode( Str )) # This code is contributed by PranchalK. |
C#
// C# program to decode a string recursively // encoded as count followed substring using System; using System.Collections.Generic; class GFG { // Returns decoded string for 'str' public static string decode( string str) { Stack< int > integerstack = new Stack< int >(); Stack< char > stringstack = new Stack< char >(); string temp = "" , result = "" ; // Traversing the string for ( int i = 0; i < str.Length; i++) { int count = 0; // If number, convert it into number // and push it into integerstack. if ( char .IsDigit(str[i])) { while ( char .IsDigit(str[i])) { count = count * 10 + str[i] - '0' ; i++; } i--; integerstack.Push(count); } // If closing bracket ']', pop elemment // until '[' opening bracket is not found // in the character stack. else if (str[i] == ']' ) { temp = "" ; count = 0; if (integerstack.Count > 0) { count = integerstack.Peek(); integerstack.Pop(); } while (stringstack.Count > 0 && stringstack.Peek() != '[' ) { temp = stringstack.Peek() + temp; stringstack.Pop(); } if (stringstack.Count > 0 && stringstack.Peek() == '[' ) { stringstack.Pop(); } // Repeating the popped string 'temo' // count number of times. for ( int j = 0; j < count; j++) { result = result + temp; } // Push it in the character stack. for ( int j = 0; j < result.Length; j++) { stringstack.Push(result[j]); } result = "" ; } // If '[' opening bracket, push it // into character stack. else if (str[i] == '[' ) { if ( char .IsDigit(str[i - 1])) { stringstack.Push(str[i]); } else { stringstack.Push(str[i]); integerstack.Push(1); } } else { stringstack.Push(str[i]); } } // Pop all the elmenet, make a // string and return. while (stringstack.Count > 0) { result = stringstack.Peek() + result; stringstack.Pop(); } return result; } // Driver Code public static void Main( string [] args) { string str = "3[b2[ca]]" ; Console.WriteLine(decode(str)); } } // This code is contributed by Shrikant13 |
Output:
bcacabcacabcaca
<!—-Illustration of above code for “3[b2[ca]]”>
<!—->
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments