1. Write an algorithm that reads in a sequence of characters and prints them in
ID: 673765 • Letter: 1
Question
1. Write an algorithm that reads in a sequence of characters and prints them in reverse order
2. Implement a queue using two stacks.
3. Write an algorithm that read s in a sequence of characters representeing a sequence of (right and left) parenthesis and re turns 1 if the parenthesis are ba lanced (0 if they are not). For instance the sequence “(( )())” should return 1 and the sequence “(()” should return 0.
4. Write the algorithm to implement the Qu eue method DequeueKTimes(k). This method should dequeue the first k elements or all the elements if the queue containes less than k elements.
Explanation / Answer
1)
1)
2)
void QUEUEput(x): push element x onto stack A
int QUEUEget(void):
if stack B is empty
pop all elements from A and push onto B
pop element from B and return
int QUEUEisempty(void):
return true if both stack A and B are empty
//for reverse the value
read character
while ((c = getchar()) != EOF)
push character in stack
Check stack is not empty (!STACKisempty)
Then repeatedly pop from stack until stack get empty
then print the reverse value
end
3) 1) Declare a character stack S.
2) Now traverse the expression string exp.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
b) If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
After complete traversal, if there is some starting bracket left in stack then “not balanced”
4)
Input: Array A[1..n], of elements in arbitrary order; n
Output: Array A[1..n] of the same elements, but in the non-decreasing order.
Algorithm:
DequeueKTimes(k)
// insert all elements into PQ
for i = 1 to n
PQ.insert(A[k])
for k = 1 to n
// remove all elements from PQ in order
A[k] <-- PQ.remove_min()
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.