using single library
#include<iostream>
make a program ,
which takes infix ,
1st converts into postfix and then calculate
Answers
Answered by
1
Remember those pesky equations that baffled you in like 1st grade? Addition and subtraction along with their friends multiplication and division. Hey, you wanted to go play kick ball or chase that girl around the playground… not to hook up with her but to put dirt in her hair. Well, you probably learned to write your equations in infix form like 3 + 4 or 2 * 7. This makes it easy for us as humans to read and understand, but can be a bit of a pain for that simple calculator program you are trying to write. Now if we could convert those equations to postfix, we could then make things a bit simpler. So here I am going to show you a simple program, easy to modify and extend, but verbose enough to be easy to understand… right here on the Programming Underground!
Most examples on the net show you a simple program with a ton of complex algorithms or funky coding mixed up with a bunch of single letter variables to show you the concept. They do this to make it compact as well as being able to say “Look at my leet converter and it was only done in 10 lines!” That is all nice to show off to your friends, but leaves people learning out in the cold.
If you are not familiar with postfix format, think of it as taking the operators and moving them to after the operands they work on. Thus 3 + 4 would be 34+. The expression A * B + C / D would become A B * C D / +. This format is a bit easier to then parse and was designed to utilize a stack structure and reduce the need to access memory. This format is also known as “polish notation” and before you ask, yes there is a prefix notation too.
The idea behind the conversion is to again, utilize a stack and a string. By looping through the input expression and evaluating each character as we go, we can decide to either put the character on the stack of operators or tack it onto a string we build as we go. In certain situations we consider operator precedence (which one is more important) to decide what needs to be taken off the stack and placed back on. I suggest you quickly review which operators have precedence of others in C++ before continuing.
In the example below I have created 3 simple helper functions to evaluate some characters and then our main function which will simply loop through our expression and use the helpers to figure out what to do with them. This program handles +, -, * and / but could easily be extended to handle any binary operator (that is an operator that works on two values or operands). + is a binary operator because when you write 2 + 4, it is working on adding two values… 2 and 4.
So we have one function that first checks if the character is an operator. It is a simple true/false function. We also have one that checks if it is an operand. If it is not an operator or parenthesis, it is assumed to be an operand. Lastly we have a helper function that compares operators to quickly decide which one has higher precedence. It takes in two operator characters and essentially says that if the second operator has higher precedence than the first operator, say it is greater than. If not, it is less than. Otherwise they are equal. Not too bad to understand really.
Now that we have these three helper functions, all that is left is to run through the string the user enters and run through the conversion rules. If it is an operand, add it to the string. If it is an operator, we are going to check our operator stack and compare the value on the top of the stack. It compares our operator to the one on the stack, popping them off the stack and adding to the string until the stack is empty, an open parenthesis or of greater precedence.
After that, all that is left is test if it is a parenthesis. If it is opening parenthesis, we can push it right onto the stack. If it is a closing one, then we are going to keep popping off operators until we meet up with the opening one to form the match. The last bit checks that if our expression has been completely parsed...
Most examples on the net show you a simple program with a ton of complex algorithms or funky coding mixed up with a bunch of single letter variables to show you the concept. They do this to make it compact as well as being able to say “Look at my leet converter and it was only done in 10 lines!” That is all nice to show off to your friends, but leaves people learning out in the cold.
If you are not familiar with postfix format, think of it as taking the operators and moving them to after the operands they work on. Thus 3 + 4 would be 34+. The expression A * B + C / D would become A B * C D / +. This format is a bit easier to then parse and was designed to utilize a stack structure and reduce the need to access memory. This format is also known as “polish notation” and before you ask, yes there is a prefix notation too.
The idea behind the conversion is to again, utilize a stack and a string. By looping through the input expression and evaluating each character as we go, we can decide to either put the character on the stack of operators or tack it onto a string we build as we go. In certain situations we consider operator precedence (which one is more important) to decide what needs to be taken off the stack and placed back on. I suggest you quickly review which operators have precedence of others in C++ before continuing.
In the example below I have created 3 simple helper functions to evaluate some characters and then our main function which will simply loop through our expression and use the helpers to figure out what to do with them. This program handles +, -, * and / but could easily be extended to handle any binary operator (that is an operator that works on two values or operands). + is a binary operator because when you write 2 + 4, it is working on adding two values… 2 and 4.
So we have one function that first checks if the character is an operator. It is a simple true/false function. We also have one that checks if it is an operand. If it is not an operator or parenthesis, it is assumed to be an operand. Lastly we have a helper function that compares operators to quickly decide which one has higher precedence. It takes in two operator characters and essentially says that if the second operator has higher precedence than the first operator, say it is greater than. If not, it is less than. Otherwise they are equal. Not too bad to understand really.
Now that we have these three helper functions, all that is left is to run through the string the user enters and run through the conversion rules. If it is an operand, add it to the string. If it is an operator, we are going to check our operator stack and compare the value on the top of the stack. It compares our operator to the one on the stack, popping them off the stack and adding to the string until the stack is empty, an open parenthesis or of greater precedence.
After that, all that is left is test if it is a parenthesis. If it is opening parenthesis, we can push it right onto the stack. If it is a closing one, then we are going to keep popping off operators until we meet up with the opening one to form the match. The last bit checks that if our expression has been completely parsed...
Similar questions