Infix, Prefix and Postfix Expressions

Hello students, welcome to Kwickprep. You read two plus three into four and know to multiply first. How does a computer know that? Today we learn three ways to write an expression. We convert between them, and evaluate postfix with a stack.

First, two words. An operand is a value, like A or five, and an operator is a symbol, like plus. In infix, the operator sits between the two operands. This is how we write maths in class. In prefix, the operator comes before its operands. Prefix is also called Polish notation. In postfix, the operator comes after its operands. Postfix is also called reverse Polish notation.

So why should a computer care? Infix is easy for us, but the computer must remember precedence rules and match brackets. Precedence means which operator is done first, like multiply before add. Prefix and postfix never need brackets, because the order of operators already shows what happens first. Postfix can be read just once, from left to right, using a stack. That is why compilers and calculators turn infix into postfix before they calculate.

Before converting, recall the precedence order. Brackets are always solved first. The caret sign stands for power in these exam questions. In real Java code the caret means bitwise X O R, and you use Math dot pow for power. Next come multiply, divide and remainder. Add and subtract come last. Operators of equal precedence are taken from left to right, except power, which goes right to left.

Now let us convert A plus B into C to postfix. Multiply has higher precedence, so B into C is done first, and becomes B C star. Next we add A to that part, so the plus goes after both operands. Finally we remove the brackets, and the answer is A B C star plus.

Now watch what brackets change. Here A plus B is inside brackets, so it is done first and becomes A B plus. Then that whole part is multiplied by C, so the star goes at the end. Removing the brackets gives A B plus C star. Compare it with the last slide, the operators now appear in a different order.

Prefix uses the same steps, but each operator moves in front of its operands. A plus B becomes plus A B. For A plus B into C, B into C becomes star B C. Then plus goes in front, giving plus A star B C. For bracket A plus B, into C, we get star plus A B C. Notice that the operands A, B and C never change their order, only the operators move.

Now evaluation, which means finding the value. A stack is a pile where the last item put in is the first one taken out, like a pile of plates. We read the postfix expression from left to right. When we see an operand, we push it, which means we put it on top. When we see an operator, we pop two values off the top, and the second value popped is the left operand. We calculate and push the answer back. When the expression ends, the single value left on the stack is the answer.

Let us evaluate two three four star plus. Read two, and push it. Read three, and push it. Read four, and push it, so the stack holds two, three and four. Read star, pop four and three, multiply to get twelve, and push twelve. Read plus, pop twelve and two, add to get fourteen, and push it. The answer is fourteen, the same as two plus three into four.

Here is a trap that costs marks. Take eight two minus. Push eight. Push two. At minus, we pop two first and then eight, and eight is the left operand. So the answer is eight minus two, which is six, not minus six.

Now two questions of the type that appear in exams. Convert bracket A plus B, into bracket C minus D. The postfix is A B plus C D minus star, and the prefix is star plus A B minus C D. Next, A into B plus C by D. The postfix is A B star C D slash plus, and the prefix is plus star A B slash C D.

Evaluate five six two plus star twelve four slash minus, using a stack. Push five, six and two. Plus pops two and six, and pushes eight. Star pops eight and five, and pushes forty. Push twelve and four, then slash pops them and pushes three. Minus pops three and forty, and forty minus three gives thirty seven.

Pause the video and try these two. First, evaluate nine three slash two plus. Second, write the prefix form of A minus B into C. Answers: nine by three is three, plus two is five. The prefix is minus A star B C.

A few tips for full marks. Examiners give step marks, so show every step. For evaluation, draw a table of the stack after each symbol. Never change the order of the operands. Finally, check your postfix answer by solving the original infix with small numbers.

Let us revise. Infix puts the operator between, prefix before, and postfix after the operands. Prefix and postfix need no brackets, so computers prefer them. To convert, follow precedence and move each operator. To evaluate postfix, push operands, and at an operator pop two values. The second value popped is always the left operand. Practise with five expressions of your own today.