Evaluate PreFix Expression

We have already written algorithm to convert infix expression to post fix expression. You can refer my previous post for the same. As we have already having a prefix expression and that is well known to computer, let's directly jump on to the algorithm.

Algorithm:

1. Reverse the expression.
2. Tokenize the expression depending on the delemeter.
3. Perform the following operations on each token.
1. If token is operand, push the token to the stack
2. If token is operator.
1. Do two pops on stack. First one being operand 1 and second one being operand 2.
2. Create an expression operand 1 + token + operand 2 and evaluate. 
3. Push the result in stack again.
4. Pop the stack for the result.

Time Complexity : O(N^2)

Difference against the Post Fix Evaluation :

1. We have to reverse in the first instance.
2. In prefix evaluation we have to treat the first pop as operand 1 and second pop as operand 2 unlike post fix evaluation

Algorithm Execution:

Input Expression : + 1 * 2 3

Step 1 : + 1 * 2 3 => 3 2 * 1 +

Step 2 : Stack[3]

Step 3 : Stack[3, 2]

Step 4 : Stack[6]

Step 5 : Stack[6,1]

Step 5 : Stack[7] - Result

Time Complexity : O(N)

You can fork the source code and unit tests from github.

Read More

Evaluate Post Fix Expression

We have already written algorithm to convert infix expression to post fix expression. You can refer my previous post for the same. As we have already having a post fix expression and that is well known to computer, let's directly jump on to the algorithm.

Algorithm:

1. Tokenize the expression depending on the delemeter.
2. Perform the following operations on each token.
1. If token is operand, push the token to the stack
2. If token is operator.
1. Do two pops on stack. First one being operand 2 and second one being operand 1.
2. Create an expression operand 1 + token + operand 2 and evaluate. 
3. Push the result in stack again.
3. Pop the stack for the result.

Time Complexity : O(N)

Algorithm Execution:

Input Expression : 1 2 3 * +

Step 1 : Stack[1]

Step 3 : Stack[1, 2]

Step 4 : Stack[1,2,3]

Step 5 : Stack[1,6]

Step 5 : Stack[7] - Result

You can fork the source code and unit tests from github.

Read More

Evaluate a mathematics expression in java

Read More

Infix to Prefix

In my previous post we evaluated the algorithm to convert a prefix expression to post fix expression. Infix to Post fix algorithm is going to be handy for writing the algorithm of Infix to Prefix. We just need few additional steps to do so. But before jumping on to the solution for computer program, let's first solve it in a mathematical way. 

Before just jumping on to the algorithm and implementation, let's start slow. I am going to convert a infix expression first in a traditional mathematical way and then will derive the algorithm using computer language. Let me start with a simple example.

Order Of Operation

1. Parenthesis - ( ) { } [ ]
2. Exponent (Right to left)
3. Multiplication and Division (Left to Right)
4. Addition and Subtraction (Left to Right)

Given Infix Expression : A + B * C

Steps:

1. First manually put the parenthesis depending on the operator precedence.
2. Then start evaluating from the inner most expression.
3. Remove the parenthesis.

A + B * C -> A + ( B * C ) -> A + ( * B  C ) -> + A ( * B C )  + -> + A * B C

Final Result : + A * B C

Now let directly jump on to the computer algorithm. I will not be writing the infix to post fix algorithm here. Please refer my previous post for the same.

Algorithm:

1. Reverse the input expression
2. Change all open parenthesis to close and visa versa. 
3. Run the infix to post fix algorithm
4. Reverse the output

Time Complexity : 

Time Complexity of infix to post fix + O(n) + O(n) + O(n)

=>(O(n+m)) + O(m)) + O(n) + O(n) + O(n) where n =  no of tokens, m = stack size

You can also fork the code from github.

Read More

Infix to Post Fix

Before just jumping on to the algorithm and implementation, let's start slow. I am going to convert a infix expression first in a traditional mathematical way and then will derive the algorithm using computer language. Let me start with a simple example.

Order Of Operation

1.  Parenthesis - ( ) { } [ ]
2.  Exponent (Right to left)
3. Multiplication and Division (Left to Right)
4. Addition and Subtraction (Left to Right)

Given Infix Expression : A + B * C

Steps:

1. First manually put the parenthesis depending on the operator precedence.
2. Then start evaluating from the inner most expression.
3. Remove the parenthesis.

A + B * C -> A + ( B * C ) -> A + ( B  C * ) -> A ( B C * )  + -> A B C * +

Final Result : A B C * +

Now let's solve the problem using computer language and we are going to take the help of the stack to solve this problem. Why we opted for a stack ADT? Good question and I believe, the next explanation will clarify your answer. So let's not jump on that question now. 

Given Infix Expression : A + B * C

We are going to use the following use the following components for the algorithm.

1. Stack
2. String

Algorithm :

1. Tokenize the expression depending on the delemeter.
2. Perform the steps for each of the token
1. If token is an operand append to the result string
2. If token is an operator peek the stack, check if operator and check for the operator precedence
1. pop the stack till stack has operator precedence greater than equal to token precedence and append that to string.
2. else push the operator to the stack
3. If you find an open parenthesis, push that to the stack.
4. If you find an closed parenthesis, pop and append to the string till you get a open parenthesis. Then pop the open parenthesis too.
3. Pop the entire stack and append that to result string.

Time Complexity : O(n+m)) + O(m) where n =  no of tokens, m = stack size

Execution of algorithm:

Step 1 : String : A :: Stack : []

Step 2 : String : A :: Stack : [+]

Step 3 : String : AB :: Stack : [+]

Step 4 : String : AB :: Stack : [+, *]

Step 5 : String : ABC :: Stack : [+,*]

Step 6 : String : ABC*+ :: Stack : []

I took a very easy expression to keep the post simple and more understandable. You can apply the same algorithm to process your complex expressions. Now it's time to convert this algorithm steps to a program. I am using java to do so.

The complete program with github can be forked here

Read More