Class notes
Infix, Prefix, and Postfix Expressions:
- Course
- Institution
Infix, Prefix, and Postfix Expressions:
[Show more]
Seller
Follow
youtubecanvas
Content preview
Infix, Prefix, and Postfix Expressions:For simplicity, we will consider algebraic expressions with binary operators +, –, *,
and / only.
Infix Notation:
Usual notation in constructing algebraic expression such that operator appears
between two operands; it is ambiguous and requires knowledge of operator hierarchy for
its evaluation. Parentheses can also be used to override operator hierarchy.
Prefix Notation:
A special notation in constructing algebraic expression such that operator appears
before its two operands. It is unambiguous and does not require the use of parentheses or
any knowledge of operator hierarchy for its evaluation.
Postfix Notation:
A special notation in constructing algebraic expression such that operator appears
after its two operands. It is unambiguous and does not require the use of parentheses or
any knowledge of operator hierarchy for its evaluation.
Example: The infix expression ((a–b)/c)*((d+e)–f) has the following postfix and prefix
expression.
Postfix: ab–c/de+f –*
Prefix: */–abc–+def
Evaluating Postfix Expression:
scan given postfix expression;
for each symbol in postfix
if operand
then push its value onto a stack S;
if operator
then { pop operand2;
pop operand1;
apply operator to compute operand1 op operand2;
push result back onto stack S;
}
return value at top of stack;
1
, Evaluating Prefix Expression:
reverse given prefix expression;
scan the reversed prefix expression;
for each symbol in reversed prefix
if operand
then push its value onto a stack S;
if operator
then { pop operand1;
pop operand2;
apply operator to compute operand1 op operand2;
push result back onto stack S;
}
return value at top of stack;
Infix to Postfix Conversion:
given a legal infix string;
create an initially empty postfix string;
create an initially empty operator stack S;
for each symbol ch in the infix string do
if ch is an operand
then
append it to the output postfix string;
else if ch == ‘(‘
then
push ch onto stack S;
else if S == ‘)’
then
pop and append operators to output string until the matching ‘(‘ is encountered;
// discard the two parentheses
else // ch must be some other operator
{ while operator stack not empty
and precedence(top(S)) ≥ precedence(ch)
and top(S) != ‘(‘ do
pop operator;
append it to the postfix string;
end while;
push S
}
end for;
while operator stack is not empty do
pop operator;
append it to the postfix string;
endwhile;
2
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller youtubecanvas. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
75323 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now