There are three types of expressions,
- Infix :
Infix expressions are the ones where the operators are used between values, like a + b - c. - Postfix :
These are the expressions where operators are written after the values, like a b c +- , this translates to a + b - c in infix. - Prefix :
In these expressions, the operators are written before the values, for example + - a b c . This expression will also be equal to a + b - c in infix.
Okay, so what this algorithm does is evaluate expressions like ( ( 3 + 4 ) * 83 ).
It starts by breaking down this expression into a list of stings and create two empty stack, one for housing the values and other for the operators. Then we go through the list one by one. Whenever it sees a left bracket, '(' , it just continues. When it sees a number, it is pushed to the value stack and when it encounters an operation like +, -, /, *, it pushes them to the operator stack. The real magic happens when it encounters a right bracket, ')', that's when the computation takes place. We pop two values from the value stack and one operator from the operator stack, then push back the result of the operation on the two values back to the values stack. In the end we just have to return the only left value in the stack which will be the result of evaluation.
Here's how it could be framed in steps :
- Split the input into a list.
- Create two stacks, one for values and one for operators.
- Go through the list.
- Push values to the appropriate stacks
- If we encounter a right bracket, pop two values from the value stack and an operator from operator stack.
- Compute their result and push it back to the value stack
- When the loop ends, just return the value left in the stack.
This algorithm can be implemented in the following way -
Comments
Post a Comment