Scribd
Upload
2 views1 page

Stack and Recursion Functions Guide

The document outlines a series of programming tasks related to stacks and recursion in data structures. It includes redesigning the Stack ADT to support a FindMin function, evaluating and converting expressions between infix, postfix, and prefix formats, and validating matching parentheses in expressions. Additionally, it discusses recursive implementations of various functions and the potential benefits of recursion versus iteration.

Uploaded by

mohamed.most.courses
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views1 page

Stack and Recursion Functions Guide

The document outlines a series of programming tasks related to stacks and recursion in data structures. It includes redesigning the Stack ADT to support a FindMin function, evaluating and converting expressions between infix, postfix, and prefix formats, and validating matching parentheses in expressions. Additionally, it discusses recursive implementations of various functions and the potential benefits of recursion versus iteration.

Uploaded by

mohamed.most.courses
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Department of Computer Science

Stacks and Recursion Data Structures


Faculty of Computers and Information

1. Redesign the Stack ADT, along with its operations, so that it supports a function FindMin, which is Θ(1).
2. Redesign the functions EvaluatePostfix and InfixToPostfix to overcome as much limitations as you can,
then write a complete program to read an infix string and evaluate it.
3. Write 6 functions for the possible 6 conversions between Infix, Postfix, and Prefix expressions. Which of these
functions is easier if written recursively?
4. Write the function EvaluatePrefix.
5. Rewrite the functions EvaluatePrefix and EvaluatePostfix recursively.
6. In mathematical expressions, or any other expression, there can be many parentheses to group together some
operations or subparts of the expression. There are three kinds of parentheses: (, {, and [, along with their
matching ones: ), }, and ] respectively. It is required to write a function that takes a string, ending with the
null character ’\0’, and returns 1 if the string has correct matching parentheses and 0 otherwise. For example,
the string [· · · (· · ·){· · ·} · · ·] is valid. However, the string [· · · (· · ·}{· · ·}] is not valid because } is the wrong
match of (. Also, the string [· · · (· · ·){· · ·}] · · ·) is not valid, because the last ) does not match any parenthesis.
Also, the string (· · · [· · · (· · ·){· · ·}] is not valid because the first ( is not matched. Notice that, the dots in these
expressions mean any sequence of characters.
Hint: Make an empty stack. Read characters until the end of the string. If the character is an open anything,
push it onto the stack. If it is a close anything, then if the stack is empty report and error. Otherwise, pop
the stack. If the symbol popped is not the corresponding opening symbol, then report an error. At end of the
string, if the stack is not empty report an error.
7. Try to write the function recursively; can we? If you can, then draw the recursion tree and see whether you
can convert it to iterative version. Is this iterative version the same as the previous function.
8. Write the function ClearStack in the implementation level of a linked stack recursively. Draw the recursion
tree, and conclude the stack depth. Is there any need for implementing this function recursively than iteratively?

You might also like