0
What is the complexity of reverse the input string using stack?
Wiki User
∙ 8y ago
O(n*2) for n characters.
It is more efficient to simply walk from both ends of the string, swapping characters as you go, reducing the complexity to just O(n/2).
Wiki User
∙ 8y ago
Add your answer:
Earn +20 pts
How can a stack determine if a string is a palindrome?
foreach char in string push on to stack create new string foreach char in string pop off and add to end of new string if new string equals old string palindrome else not palindrome //when you pop off the stack, the characters come off in reverse order, thus you have reversed the original string
How would you write a program that takes a string of characters and reverses them in the C programming language?
void main() {char a[30] = "India"; //Let the string be stored in a[30]; char b[30]; //declaring another string for(i=0;i<strlen(a);i++) {b[strlen(a)-1 - i]=a[i];} //Now reverse string is stored in b; //to print it cout<<b; getch(); }
Infix to postfix C?
Infix Expression :Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.Postfix Expression :The Postfix(Postorder) form of the above expression is "23*45/-".Infix to Postfix Conversion :In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+. The algorithm for the conversion is as follows :Scan the Infix string from left to right.Initialise an empty stack.If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character to stack. If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.Repeat this step till all the characters are scanned.(After all characters are scanned, we have to add any character that the stack may have to the Postfix string.) If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty.Return the Postfix string.Example :Let us see how the above algorithm will be imlemented using an example.Infix String : a+b*c-dInitially the Stack is empty and our Postfix string has no characters. Now, the first character scanned is 'a'. 'a' is added to the Postfix string. The next character scanned is '+'. It being an operator, it is pushed to the stack.StackPostfix StringNext character scanned is 'b' which will be placed in the Postfix string. Next character is '*' which is an operator. Now, the top element of the stack is '+' which has lower precedence than '*', so '*' will be pushed to the stack.StackPostfix StringThe next character is 'c' which is placed in the Postfix string. Next character scanned is '-'. The topmost character in the stack is '*' which has a higher precedence than '-'. Thus '*' will be popped out from the stack and added to the Postfix string. Even now the stack is not empty. Now the topmost element of the stack is '+' which has equal priority to '-'. So pop the '+' from the stack and add it to the Postfix string. The '-' will be pushed to the stack.StackPostfix StringNext character is 'd' which is added to Postfix string. Now all characters have been scanned so we must pop the remaining elements from the stack and add it to the Postfix string. At this stage we have only a '-' in the stack. It is popped out and added to the Postfix string. So, after all characters are scanned, this is how the stack and Postfix string will be :StackPostfix StringEnd result :Infix String : a+b*c-dPostfix String : abc*+d-
What is time complexity and space complexity?
"Running Time" is essentially a synonym of "Time Complexity", although the latter is the more technical term. "Running Time" is confusing, since it sounds like it could mean "the time something takes to run", whereas Time Complexity unambiguously refers to the relationship between the time and the size of the input.
What is time complexity of stack?
All major queue operations (push, pop and front) are constant time operations.
How can a stack determine if a string is a palindrome?
foreach char in string push on to stack create new string foreach char in string pop off and add to end of new string if new string equals old string palindrome else not palindrome //when you pop off the stack, the characters come off in reverse order, thus you have reversed the original string
Which of the data structures is most efficient in terms of both space and time to reverse a string characters?
stack
What data structures is most efficient in terms of both space and time to reverse a string of characters?
Stack
Take input of string reverse the strring in python?
There are five common methods of string inversion in Python: using string slicing, using recursion, using the list reverse () method, using stack and using for loop. Use string slicing (most concise) s = "hello" reversed_ s = s[::-1] print(reversed_s) >>> olleh Use recursive def reverse_ it(string): if len(string)==0: return string else: return reverse_ it(string[1:]) + string[0] print "added " + string[0] string1 = "the crazy programmer" string2 = reverse_ it(string1) print "original = " + string1 print "reversed = " + string2 Use the list reverse() method in [25]: l = ['a', 'B', 'C','d '] ...: l.reverse() ...: print (l) ['d', 'c', 'b', 'a'] Using stack def Rev_ string(a_string): L = list (a_string) # simulate all stacking new_ string = "" while len(l)>0: new_ String + = l.pop() # simulate stack out return new_ string Use the for loop #for loop def func(s): r = "" max_ index = len(s) - 1 for index,value in enumerate(s): r += s[max_index-index] return r r = func(s) The above are the five common methods of string inversion in Python. I hope it can be helpful to your learning of Python strings
How would you write a program that takes a string of characters and reverses them in the C programming language?
void main() {char a[30] = "India"; //Let the string be stored in a[30]; char b[30]; //declaring another string for(i=0;i<strlen(a);i++) {b[strlen(a)-1 - i]=a[i];} //Now reverse string is stored in b; //to print it cout<<b; getch(); }
Infix to postfix C?
Infix Expression :Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.Postfix Expression :The Postfix(Postorder) form of the above expression is "23*45/-".Infix to Postfix Conversion :In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+. The algorithm for the conversion is as follows :Scan the Infix string from left to right.Initialise an empty stack.If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character to stack. If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.Repeat this step till all the characters are scanned.(After all characters are scanned, we have to add any character that the stack may have to the Postfix string.) If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty.Return the Postfix string.Example :Let us see how the above algorithm will be imlemented using an example.Infix String : a+b*c-dInitially the Stack is empty and our Postfix string has no characters. Now, the first character scanned is 'a'. 'a' is added to the Postfix string. The next character scanned is '+'. It being an operator, it is pushed to the stack.StackPostfix StringNext character scanned is 'b' which will be placed in the Postfix string. Next character is '*' which is an operator. Now, the top element of the stack is '+' which has lower precedence than '*', so '*' will be pushed to the stack.StackPostfix StringThe next character is 'c' which is placed in the Postfix string. Next character scanned is '-'. The topmost character in the stack is '*' which has a higher precedence than '-'. Thus '*' will be popped out from the stack and added to the Postfix string. Even now the stack is not empty. Now the topmost element of the stack is '+' which has equal priority to '-'. So pop the '+' from the stack and add it to the Postfix string. The '-' will be pushed to the stack.StackPostfix StringNext character is 'd' which is added to Postfix string. Now all characters have been scanned so we must pop the remaining elements from the stack and add it to the Postfix string. At this stage we have only a '-' in the stack. It is popped out and added to the Postfix string. So, after all characters are scanned, this is how the stack and Postfix string will be :StackPostfix StringEnd result :Infix String : a+b*c-dPostfix String : abc*+d-
What is time complexity and space complexity?
"Running Time" is essentially a synonym of "Time Complexity", although the latter is the more technical term. "Running Time" is confusing, since it sounds like it could mean "the time something takes to run", whereas Time Complexity unambiguously refers to the relationship between the time and the size of the input.
What is time complexity of stack?
All major queue operations (push, pop and front) are constant time operations.
What is a stack trace?
A 'stack trace' is a list of which functions have been called, based on this information. The stack is very inflexible about allocating memory; everything must be deallocated in exactly the reverse order it was allocated in.
Code palindrome in c using queue and stuck?
/** C Program to Check String is Palindrome using Stack.*/#include #include void push(char);char pop();char stack[100];int top = -1;void main(){char str[100];int i, count = 0, len;printf("Enter string to check it is palindrome or not : ");scanf("%s", str);len = strlen(str);for (i = 0; i < len; i++){push(str[i]);}for (i = 0; i < len; i++){if (str[i] == pop())count++;}if (count == len)printf("%s is a Palindrome string\n", str);elseprintf("%s is not a palindrome string\n", str);}/* Function to push character into stack */void push(char c){stack[++top] = c;}/* Function to pop the top character from stack */char pop(){return(stack[top--]);}
Where string is stored on Heap or Stack in java?
A String is treated as an object, meaning there is an object on the heap. Of course, the variable you define is a pointer to the object, and it is stored on the stack.A String is treated as an object, meaning there is an object on the heap. Of course, the variable you define is a pointer to the object, and it is stored on the stack.A String is treated as an object, meaning there is an object on the heap. Of course, the variable you define is a pointer to the object, and it is stored on the stack.A String is treated as an object, meaning there is an object on the heap. Of course, the variable you define is a pointer to the object, and it is stored on the stack.
Implementation of stack using recursion?
public void reverse(Stack st) { int m = (int)st.Pop(); if (st.Count != 1) reverse(st); Push(st , m); } public void Push(Stack st , int a) { int m = (int)st.Pop(); if (st.Count != 0) Push(st , a); else st.Push(a); st.Push(m); }
