In our algorithm, we\'ll use two stacks: PostFix and OpStack We\'re given an exp
ID: 3709958 • Letter: I
Question
In our algorithm, we'll use two stacks: PostFix and OpStack
We're given an expression that contains values, parentheses, and operators. To keep things simpler and focus on the general algorithm, we'l limit the algorithm to only four operations (addition, subtraction, multiplication, and division) and use this hierarchy:
multiplication and division
addition and subtraction
Note that this means that multiplication and division have the same precedence. Similarly, addition and subtraction have the same precedence as each other.
Here is the pseudocode:
while there are tokens to process
case 1: the token is a value
push the value onto the PostFix stack
case 2: the token is an operator
while the precedence of the operator currently on the OpStack >= the precedence of the current operator
Important Note 1: This is >= (not just >)- so if the operator on the top of OpStack has the same precedence as the current one, you should enter this loop!
Important Note 2: Parentheses are not considered in this part of evaluating the contents of OpStack. In this loop, you are just comparing to other operators. If you reach a parenthesis, stop.
topOp = pop the operator from the OpStack
push topOp onto the PostFix stack
push the current operator onto OpStack
case 3: the token is a left parenthesis
push the parenthesis onto the OpStack
case 4: the token is a right parenthesis
while the top element of the OpStack is not a left parenthesis
topOp = pop the operator from the OpStack
push topOp onto the PostFix stack
pop the left parenthesis off the OpStack
// there are no more tokens to process- the while loop is done
while there are still tokens on the OpStack
topOp = pop the operator from the OpStack
push topOp onto the PostFix stack
The final result will be the expression in postfix notation in the PostFix stack. (We'll look next at how you take that notation and actually evaluate it.)
Example
infix notation: a + b * c / d
token: a
action: push a onto PostFix
PostFix OpStack
a
token: +
action: push + onto Opstack
PostFix OpStack
a +
token: b
action: push b onto PostFix
PostFix OpStack
b +
a
token: *
action: the topOp + has lower precedence than *, so we push * onto OpStack
PostFix OpStack
b *
a +
token: c
action: push c onto PostFix
PostFix OpStack
c *
b +
a
token: /
action: the topOp has the same precedence as /, so we pop the topOp and push it onto the PostFix stack
PostFix OpStack
* +
c
b
a
action: the topOp now has a lower precedence as /, so we push it onto the OpStack
PostFix OpStack
* /
c +
b
a
token: d
action: push onto PostFix stack
PostFix OpStack
d /
* +
c
b
a
there are no more tokens to read
we now transfer everything from OpStack to PostFix (pop from OpStack, push to PostFix)
PostFix OpStack
+
/
d
*
c
b
a
We humans can now read the postfix notation from the bottom to the top: a b c * d / +
Question:
Convert the following infix expressions into postfix notation.
Submit your answer with a single space between each operand and operator.
A. a * b / (c + d)
B.(a - b / c ) / (d + e / f * g )
C. a * b * (c + (d - e))
Explanation / Answer
A. infix notation: a * b / (c + d)
token: a
action: Push a onto PostFix
PostFix OpStack
a
token: *
action: Push * onto OpStack
PostFix OpStack
a *
token: b
action: Push b onto PostFix
PostFix OpStack
b *
a
token: /
action: topOp has the same precedence as /, so we pop the topOp and push it onto the PostFix stack,
PostFix OpStack
*
b
a
action: OpStack is empty we can push /
PostFix OpStack
* /
b
a
token: (
action: Push ( onto OpStack
PostFix OpStack
* (
b /
a
token: c
action: Push c onto PostFix
PostFix OpStack
c (
* /
b
a
token: +
action: Push + onto OpStack
PostFix OpStack
c +
* (
b /
a
token: d
action: Push d onto PostFix
PostFix OpStack
d +
c (
* /
b
a
token: )
action: while the top element of the OpStack is not a left parenthesis
topOp = pop the operator from the OpStack
push topOp onto the PostFix stack
PostFix OpStack
+ (
d /
c
*
b
a
Pop ( from the OpStack
there are no more tokens to read
we now transfer everything from OpStack to PostFix (pop from OpStack, push to PostFix)
PostFix OpStack
/
+
d
c
*
b
a
read the postfix notation from the bottom to top a b * c d + /
B. Infix Notation: (a - b / c) / (d + e / f * g)
Similarly,
token: (
action: Push onto OpStack
PostFix OpStack
(
token: a
action: Push onto PostFix
PostFix OpStack
a (
token: -
action: Push onto OpStack
PostFix OpStack
a -
(
token: b
action: Push Onto PostFix
PostFix OpStack
b -
a (
token: /
action: topOp has lower prescendence then /, Push onto OpSack
PostFix OpStack
b /
a -
(
token: c
action: Push Onto PostFix
PostFix OpStack
c /
b -
a (
token: )
action: while the top element of the OpStack is not a left parenthesis
topOp = pop the operator from the OpStack
push topOp onto the PostFix stack
PostFix OpStack
- (
/
c
b
a
Pop ( form OpStack
token: /
action: Push onto OpStack
PostFix OpStack
- /
/
c
b
a
token: (
action: Push onto OpStack
PostFix OpStack
- (
/ /
c
b
a
token: d
action: Push onto PostFix
PostFix OpStack
d (
- /
/
a
b
c
token: +
action: Push Onto OpStack
PostFix OpStack
d +
- (
/ /
c
b
a
token: e
action: Push onto PostFix
PostFix OpStack
e +
d (
- /
/
c
b
a
token: /
action: Push Onto OpStack
PostFix OpStack
e /
d +
- (
/ /
c
b
a
token: f
action: Push onto OpStack
PostFix OpStack
f
e /
d +
- (
/ /
c
b
a
token: *
action: topOp has same precedence as *, pop topOp, and Push onto PostFix
PostFix OpStack
/
f
e +
d (
- /
/
c
b
a
Push * onto OpStack
PostFix OpStack
/
f *
e +
d (
- /
/
c
b
a
token: g
PostFix OpStack
g
/
f *
e +
d (
- /
/
c
b
a
token: )
action: while the top element of the OpStack is not a left parenthesis
topOp = pop the operator from the OpStack
push topOp onto the PostFix stack
PostFix OpStack
+ (
* /
g
/
f
e
d
-
/
c
b
a
Pop ( from OpStack
there are no more tokens to read
Pop everything from OpStack and push into PostFix stack,
PostFix OpStack
/
+
*
g
/
f
e
d
-
/
c
b
a
read the postfix notation from bottom to top: a b c / - d e f / g * + /
C. Infix Notation: a * b * (c + (d - e))
Similarly,
We can create the post fix stack using following steps:
token: a
action: Push onto PostFIx
token: *
action: Push onto OpStack
token: b
action: Push onto PostFix
token: *
action: topOp has same precedence as *, pop topOp and Push onto PostFix
Push * onto OpStack
token: (
action: Push onto OpStack
token: c
action: Push onto PostFix
token: +
action: Push onto OpStack
token: (
action: Push Onto OpStack
token: d
action: Push onto PostFix
token: -
action: Push onto OpStack
token: e
action: Push onto PostFix
token:)
action: while the top element of the OpStack is not a left parenthesis
topOp = pop the operator from the OpStack
push topOp onto the PostFix stack
Pop ( from OpStack
token: )
action: while the top element of the OpStack is not a left parenthesis
topOp = pop the operator from the OpStack
push topOp onto the PostFix stack
Pop ( from OpStack
there is not any token left to read
pop everything out from OpStack and Push onto PostFix, thus giving the PosstFix stack,
PostFix
*
+
-
e
d
c
*
b
a
thus giving the postfix notattion: a b * c d e - = *
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.