1. Introduction to Problem Domain: Prefix, Postfix & Infix Notation During our s
ID: 3615853 • Letter: 1
Question
1. Introduction to Problem Domain:
Prefix, Postfix & Infix Notation
During our studies we learn mathematics via infix notation.Our math instructors teach us to write operation symbol written betweenthe operands. Such as '-' operator between operands A and B. We solvethe expression A - B by subtracting B from A.
In some fieldsof computer science and programming languages, it makes more sense toorder expressions with different notations called prefix and postfix.Each of these three notations, prefix, postfix and infix have differentuseful attributes. They differ in how one computes the value of anexpression.
Infixnotation is most suitable for binary operations. In infix notation, theoperation symbol is written between the two operands. Because the infixnotation for the basic arithmetic and logical operations have beencommonly used in ordinary mathematics, this notation has been widelyadopted in programming languages. Infix notation use in programminglanguages may lead to unique problems. For example, when more than oneinfix operator appears in an expression, the notation is ambiguousunless parentheses are used. Consider 2 * 3 + 4. One understands thatthe value should be 10, but it could also be 14. We learned frommathematics that multiplication is performed before addition. To clearthis ambiguity, parentheses may be used to explicitly indicate thegrouping of operators and operands, which may lead to deep nests ofparentheses. Therefore, languages use implicit control rules that arecalled hierarchy of operations (precedence) and associativity.
Functioncalls are usually written with name preceding its arguments, foo (x,y). When this is extended to operations we call it the prefix notation.In prefix notation, the operator, precedes (comes before) the operandshence it is called prefix notation. It actually makes sense to know theoperation prior to receiving the arguments so that one can expect theproper number of operands. There is no ambiguity, and no parenthesesare need to specify how to evaluate the expression. Prefix notation issometimes called Polish notation because of the inventor Polishmathematician Lukasiewicz. The prefix notation is easy to decodemechanically. So, it is simple to translate code into sequences. Forexample given the prefix expression P consisting of operators andoperands we can evaluate the expression with a stack:
1.If the next item in P is an operator, push it on top of the stack. Setthe argument count to be the number of operands expected by theoperator.
2. If the next item in P is an operand, push it on top of the stack.
3.If the top n entries in the stack are operand entries needed for thetop operator, apply the top operator to these operands. Replace theoperator and its n operands by the result of the operation.
While this is fairly simple we have to check if we have enough operands to satisfy the current top operator.
Withpostfix notation, you place the operator after the operands. When anoperator is scanned its operands are already evaluated. Therefore thestack evaluation is as follows:
1. If the next item of P is an operand, place it on the stack.
2.If the next item of P is an operator, then its n arguments must be thetop n items on the stack. Replace these n items by the result ofapplying this operation using the n items as arguments.
So,postfix evaluations are easier to implement using a stack. Often thesyntax of expressions is converted to postfix during code translation.
Infix
Prefix
Postfix
(A + B)/D
/+ABD
AB+D/
(A + B)/(D + E)
/+AB+DE
AB+DE+/
(A - B/C + E)/(A+B)
Infix
Prefix
Postfix
(A + B)/D
/+ABD
AB+D/
(A + B)/(D + E)
/+AB+DE
AB+DE+/
(A - B/C + E)/(A+B)
Explanation / Answer
What are you actually confused about? That is a lot of informationand you could need help with a lot of things.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.