math expression

Evaluating a regular mathematical expression is a common task in computers. The process usually involves two steps:

1. convert a string notation (which is infix) to postfix notation.

2. actually evaluate the result from postfix notation.

Since both steps use stack, it is a common practice exercise in learning stack programming. We use it in our lab too.

Objectives:

• 1. Use infix to postfix conversion as an example to illustrate there are more than one way to implement identical algorithm.

  2. Compare solutions from the textbook and my modification (for better or for worse).

  3. My hope is that it will encourage you to explore and experiment various programming styles and try to find one that you're most comfortable.

  4. Understanding other people's code and make "improvements" to it is an essential engineering skill.

Definitions:

I prefer reading switch code versus if then else. How about you? If you feel the same way, then we shall walk the talk. Did you notice that the precedence of ( is lowest? Why?

convertToPostfix() -- operand

One of the enhancement I did is to handle both numbers and variables in the expression. The code with red arrow is the only change needed. If the char is alpha or numeric (isalnum) or the char is dot (floating point) then it is considered as operand or part of operand. Other than that, the char is considered as operator which is processed by the switch(ifx[i]) statement.

Note that the original infixToPostFiximp.cpp code on the right has a bug in clearing the oprStack. It is fixed with "while" loop on the left. (Ali spots the bug. red dot circle)

I also insert a space into the postfix string before every operator (blue arrow line). Try comment it out and see what happens to the output.

parenthese operators processing

For the left parenthesis ( , we just push it onto the operator stack. For right parenthesis ) , we need to pop all operators until corresponding left parenthesis is encountered. The code on the right and left achieve the same result. It is just a different style of programming. If you have other approaches, please share.

all other operator processing

The default case processes all other operators. At the moment, it only takes care of + - * / . The algorithm does two things: if stack is empty, push it onto stack. If that's not the case, pop all higher or equal precedence operators out of the stack, then push current operator.

Again, both codes perform the same algorithm. Reading other people's solution is a privilege. We can learn, improve, and share again. That's healthy for the community.

another approach to operator processing

After one night sleep, I changed above implementation a bit. Instead of a compound while condition, I move precedence comparison to if statement. Hopefully, it makes it easy to read. Is it? Another side benefit is the precedence routine becomes simpler. We do need to change the return code from bool to int though.

Output

The following image is the result from the modified implementation. It produces the same postfix as the textbook exercise. The last line output shows that it can support floating points and numeric operand. So, remember the blue arrow line above? What would the output be?

Discussions:

• 1. Support different operand type is not hard at all, we just push it out to postfix. However, evaluation of the expression could be a different story. If you like to explore further, I recommend that you add an eval() function to the mathExp class.

  2. What about multi-character operators, like mod? One simple approach is to go through the infix and convert all multi-character operators to a single character, e.g. change mod to %. It is also popular to use string class to separate out each operand and operators.