Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

STACKS
1
...

Stack ADT is an ordered list in which all insertions and deletions are made at one end called
TOP
...

Stack is a Last-In First-Out (LIFO) data structure
...


Following operations can be performed on a stack
...
PUSH: PUSH operation will add elements onto the stack
...

Add element onto the location of stack pointed by top
...
POP: This operation will remove elements from stack
...






Check whether there is at least one element in the stack, to avoid STACK
UNDERFLOW
...
Write the algorithm to convert an infix expression to postfix expression and explain it
with an example
...

Postfix Expression: The Postfix (Postorder) form of the above expression is "23*45/-"
...
The corresponding postfix notation is
abc*+
...

2
...

4
...

Initialize an empty stack and a Postfix string
...

If the scanned character is an operator,
a
...

b
...

c
...

5
...

(After all characters are scanned, we have to add any character that is in the stack to the
Postfix string
...
If stack is not empty add topStack to Postfix string and Pop the stack
...

7
...

Example :
Let us see how the above algorithm will be implemented using an example
...
Now, the first character
scanned is 'a'
...
The next character scanned is '+'
...
(Since stack is empty initially, precedence of top of stack
is considered to be less than precedence of ‘+’)

2 Lecture Notes prepared for II/IV CSE, RVR&JC CE

Next character scanned is 'b' which will be placed in the Postfix string
...
Now, the top element of the stack is '+' which has lower precedence
than '*', so '*' will be pushed to the stack
...
Next character scanned is '-'
...
Thus '*' will
be popped out from the stack and added to the Postfix string
...
Now the topmost element of the stack is '+' which has equal priority to '-'
...
The '-' will be pushed to the stack
...
Now all characters have been scanned
so we must pop the remaining elements from the stack and add it to the Postfix string
...
It is popped out and added to the Postfix string
...
Write the algorithm for evaluating the given postfix expression and explain it
...
Scan the Postfix string from left to right
...
Initialize an empty stack
...
If the scanned character is an operand, add it to the stack
...
If the scanned character is an Operator, then pop the top most element of the
stack(topStack) into a variable temp
...
Let the
result of this operation be retVal
...

5
...

6
...
Return
topStack
...

Postfix String : 123*+4Initially the Stack is empty
...
Thus they will be pushed into the stack in that order
...
Thus, we pop the top two elements
from the stack and perform the "*" operation with the two operands
...


The value of the expression (2*3) that has been evaluated (6) is pushed into the stack
...
Thus, we pop the top two elements
from the stack and perform the "+" operation with the two operands
...


The value of the expression (1+6) that has been evaluated (7) is pushed into the stack
...


Next character scanned is "-", which is an operator
...
The second operand
will be the first element that is popped
...


5 Lecture Notes prepared for II/IV CSE, RVR&JC CE

Now, since all the characters are scanned, the remaining element in the stack (there will be
only one element in the stack) will be returned
...
Explain how to use a stack for delimiter matching?
Arithmetic expressions such as (2 + 3 / [4+3 – {6 * 4}] + 8) uses delimiters like ( ), [ ], { } to
specify the order of operations
...
Matched delimiters in this context means that each opening symbol has a
corresponding closing symbol and the pairs of symbols are properly nested
...

Following are the steps of the algorithm for delimiter matching using a stack:
1
...

2
...

3
...

4
...
If it is not report error and terminate the process
...

5
...
If it is not report error and terminate the
process
...

6
...
If it is not report error and terminate the
process
...

7
...

8
...
Else, report that the
expression has delimiters matched
...
The first character scanned is ‘(‘
...


The next four characters scanned are ‘a’, ‘+‘, ‘b’, and ‘/’
...
Next character scanned is ‘[‘
...


After the next four characters, which are not delimiter characters, character ‘{‘will be
pushed onto the stack
...
The next character scanned is ‘}’
...


7 Lecture Notes prepared for II/IV CSE, RVR&JC CE

After ‘+’ and ‘r’, the next character scanned is ‘]’
...


The next character scanned is ‘)’, which is matching delimiter for the symbol on the top of
the stack
...


Since all the characters of the input expression are scanned, and stack is empty, the
message ‘DELIMETERS MATCHED’ will be reported and the process gets terminated

---