Trusted answers to developer questions

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Conventional notation, such as $A + B$, is equivalent to infix notation. **Postfix notation**, also known as Reverse Polish notation, is a notation where the operands appear before their operators such as in the expression $AB+$. The advantage of postfix notation is the unambiguity of the sequence of operations. In fact, parentheses are redundant in the notation.

Stacks are ideal data structures for converting infix to postfix expressions. We scan the infix expression from left to right and make decisions based on if the scanned symbol (generally called a â€˜tokenâ€™) is an operand or an operator. **Operands** are pushed to the output and **operators** are pushed to the stack; so, our decision is based on the precedence of the operator.

- Set the precedence of operations (a typical precedence set is shown in the illustration above).
- If the token is an operand, then do not push it to stack. Instead, pass it to the output.
- If the token is an operator or parenthesis, do the following:

- Before you can push the operator onto the stack, you have to pop the stack until you find an operator with a lower priority than the current operator. The popped stack elements are written to output.
- When youâ€™ve found the appropriate position, stack the current operator.
- If your current token is a right parenthesis, pop the stack until after the first left parenthesis. Output all the symbols except the parentheses.

A left parenthesis on the stack is only removed if an incoming right parenthesis is found (unlike other operators such as + - ? *, that only follow precedence rules).

- After the entire expression is scanned, pop the rest of the stack and write the operators in the stack to the output.

In the example below, we will look at how to convert the infix expression $4^2 + 5 * ( 2 + 1) / 2$ to postfix:

RELATED TAGS

notation

postfix

infix

Copyright Â©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring

Related Courses