Using C++

Infix ? Postfix conversion

Another function we looked at was one that used a stack to evaluate a postfix arithmetic expression you can review the code at the PPTs we discussed in class. As we learned we regularly using infix expressions as 5 * (3 + 4)), however, the function seems to be of limited use. The good news: we can use a stack to convert an infix expression to postfix form!

To do so, we will use the following algorithm:

Start with an empty list and an empty stack. At the end of the algorithm, the list will contain the correctly ordered tokens of the postfix expression.

Next, for each token in the expression (split on whitespace):

if the token is a digit, simply append it to the list; else, the token must be either an operator or an opening or closing parenthesis, in which case apply one of the following options:

if the stack is empty or contains a left parenthesis on top, push the token onto the stack.

if the token is a left parenthesis, push it on the stack.

if the token is a right parenthesis, pop the stack and append all operators to the list until you a left parenthesis is popped. Discard the pair of parentheses.

if the token has higher precedence than the top of the stack, push it on the stack. For our purposes, the only operators are +, -, *, /, where the latter two have higher precedecence than the first two.

if the token has equal precedence with the top of the stack, pop and append the top of the stack to the list and then push the incoming operator.

if the incoming symbol has lower precedence than the symbol on the top of the stack, pop the stack and append it to the list. Then repeat the above tests against the new top of stack.

After arriving at the end of the expression, pop and append all operators on the stack to the list.

Consider only tokens as (,),+,-,*,/