Hello all. I am a CS major and I am learning recursion right now and have a lab assignment to write a program that uses recursion to evaluate post fix expressions. I have made an attempt at this but I am stuck and need some help. Here is what I have so far. I started by writing a function that took a simple expression in ex(24+) and output an answer(6). Now to make it recursive to evaluate more complex expressions. I have made it work part way. For instance if you input 2*(6+4) as 264+* you get an output of 10. So I feel I am headed in the right direction as it should first evaluate (6+4) and it gets that right but now I can't figure out how to make it do the next step. Any help is appreciated.

Here is code....

``````int postfix(string s){
cout<<s<<endl; // for debug
int a, b;
if (s.length() == 3 && !isdigit(s[s.length()-1] && isdigit(s[s.length()-2]))){
cout<<s<<endl; // for debug
a = s[0]-48;
b = s[1]-48;
cout<<"eval "<<a<<" "<<s[2]<<" "<<b<<endl;
switch (s[2]) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
default :
}
} else {
return postfix(s.substr(1,s.length()-2));
}
return 0; // This return is for debug
}``````

Here is sample output....
Enter postfix expression: 264+*
264+*
64+
64+
eval 6 + 4
264+* = 10.

I have little bit modified your code and it is working. The only drawback is that it cannot handle more than one digit nos. at any point of time during calculation.
I have commented the code and am sure that you will understand it.
Though, I will explain it completely in a short while.

``````#include<iostream>
#include<string>
#include<sstream>
using namespace std;
//stringify just converts a int to string
inline string stringify(double x)
{
ostringstream o;
if (!(o << x))
return o.str();
}

int postfix(string s)
{
cout<<"New Postfix:"<<s<<endl; // for debug
int a, b;
if (s.length() == 3 && !isdigit(s[s.length()-1] && isdigit(s[s.length()-2])))
{
cout<<"Inside If:"<<endl; // for debug
a = s[0]-48;
b = s[1]-48;
cout<<"eval "<<a<<" "<<s[2]<<" "<<b<<endl;
switch (s[2])
{
case '+':

return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
default :
}
}
else
{
cout<<"theElsepart:"<<s.substr(1,3)<<endl;//ForDebugging
//This needs explaination:
//Lets say the the expression was "262/3*+"
//Now, I am replacing the "62/" to its value by
//calling postfix() again on "62/"

return postfix(s.replace(1,3,stringify(postfix(s.substr(1,3)))));
}
return 0; // This return is for debug
}
int main()
{
cout<<postfix("263+*");
}``````

Postfix notation is evaluated from left to right.
What your algo was: if say the expression is 22/2+1+, you were calculating 2/2+1 first. which ofcourse dont make any sense.
Rather you should calculate 22/ first and then replace it in the main expression by its value(which is 1).

So, here is your code with few modification. Comments has been added. If you need more explanation, reply here. The only draw back is that at no point of time, the value of any expression exceed one digit.

``````#include<iostream>
#include<string>
#include<sstream>
using namespace std;
//stringify just converts a int to string
inline string stringify(double x)
{
ostringstream o;
if (!(o << x))
return o.str();
}

int postfix(string s)
{
cout<<"New Postfix:"<<s<<endl; // for debug
int a, b;
if ( !isdigit(s[2]) && isdigit(s[0]))//check if the first three charactrs can be evaluated
{
//now if the length is greater than three, replace the first three with the value
if (s.length() > 3 )
return postfix(s.replace(0,3,stringify(postfix(s.substr(0,3)))));
else if (s.length()==3)//elseif the length is 3
{

cout<<"Inside If:"<<endl; // for debug
a = s[0]-48;
b = s[1]-48;
cout<<"eval "<<a<<" "<<s[2]<<" "<<b<<endl;
switch (s[2])
{
case '+':

return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
default :

}
}
else //just a error check in case ;)
cout<<"Too short to evaluate(min is 3)";

}

else
{
cout<<"theElsepart:"<<s.substr(1,3)<<endl;//ForDebugging
//This needs explaination:
//Lets say the the expression was "262/3*+"
//Now, I am replacing the "62/" to its value by
//calling postfix() again on "62/"

return postfix(s.replace(1,3,stringify(postfix(s.substr(1,3)))));
}
return 0; // This return is for debug
}
int main()
{
cout<<postfix("22/2+1+");
}``````

The only draw back is that at no point of time, the value of any expression exceed one digit.

unfortunately then it would fail to evaluate his original expression of
264+* ...right?

Yes, of course.
But I cannot help it. My job was to modify his code, not write it.
This catch is even in his original code so I cannot help. If he shows some efforts regarding multi-digits evaluation, I will surely help.
Using stack was a good idea to target such issue but then, he want it do recursively.:icon_smile:

Thanks to everyone for input. It is appreciated. I do not understand some of the things you guys are talking about. I am in a relatively early learning stage. I don't know what a stack is and I am using recursion because that's what the assignment is.

"For this lab assignment, you need to write a program that reads a postfix arithmetic expression (assuming that all operands in this expression are single-digit positive integers), and uses a recursive function to evaluate the expression and print out the result. "

Anyway I gave this alot of thought today and realized I need to store the numbers somewhere for complicated equations. So I have put my function in a class to make it easier for each recursion to access an array and counter. This is what I came up with...
(Please excuse all of the debug couts. They will be removed before project is submitted)

``````# include <iostream>
# include <string>
using namespace std;

# define MAX_SIZE 50

class Calculator{
public:
Calculator(); // default constructor
int postfix(string s); // recursive function for evaluating postfix equations
private:
int index;
int the_array[MAX_SIZE];
};

int main(){
Calculator eval;
int choice, sum;
bool quit = false;
string pf_eq = "912+/";
cout<<"This program will take a postfix expression as input, evaluate it, then output the result.\n";
do {
cout<<"\nMake selection\n";
cout<<"1 Evaluate a postfix expression\n";
cout<<"2 Quit\n";
cin>>choice;

switch (choice){
case 1:
cout<<"Enter postfix expression: ";
cin.clear();
cin>>pf_eq;
cout<<pf_eq<<" = "<<eval.postfix(pf_eq)<<".\n";
break;
case 2:
cout<<"Thanks for using the postfix evaluation program!\n";
quit = true;
break;
default:
}
} while (!quit);

}

Calculator::Calculator(){ // default constructor
index = 0;
}

int Calculator::postfix(string s){
cout<<"eval = "<<s<<endl;
int a, b;
if (s.length() == 0 ){
index = 0;
return the_array[0];
} else if (isdigit(s[0])){
cout<<"storing "<<s[0]<<" to index "<<index<<endl;
the_array[index] = s[0]-48;
index++;
return postfix(s.substr(1,s.length()-1));
} else {
a = the_array[index-2];
b = the_array[index-1];
switch (s[0]) {
case '+':
cout<<" should be "<<a<<" "<<s[0]<<" "<<b<<endl;
cout<<"replacing "<<the_array[index-2]<<" at index "<<index-2<<"with "<<a + b<<endl;
the_array[index-2] = a + b;
cout<<"Array index "<<index-2<<" is "<<the_array[index-2]<<endl;
break;
case '-':
cout<<" should be "<<a<<" "<<s[0]<<" "<<b<<endl;
cout<<"replacing "<<the_array[index-2]<<" at index "<<index-2<<"with "<<a + b<<endl;
the_array[index-2] = a - b;
cout<<"Array index "<<index-2<<" is "<<the_array[index-2]<<endl;
break;
case '*':
cout<<" should be "<<a<<" "<<s[0]<<" "<<b<<endl;
cout<<"replacing "<<the_array[index-2]<<" at index "<<index-2<<"with "<<a + b<<endl;
the_array[index-2] = a * b;
cout<<"Array index "<<index-2<<" is "<<the_array[index-2]<<endl;
break;
case '/':
cout<<" should be "<<a<<" "<<s[0]<<" "<<b<<endl;
cout<<"replacing "<<the_array[index-2]<<" at index "<<index-2<<"with "<<a + b<<endl;
the_array[index-2] = a / b;
cout<<"Array index "<<index-2<<" is "<<the_array[index-2]<<endl;
break;
default :
}
index = index-1;
cout<<"index is now "<<index<<endl;
return postfix(s.substr(1,s.length()-1));
}
return the_array[0];
}``````

This seems to work fine and will evaluate long equations fine but now I am stuck on the last part of the lab. We were given examples of what the program should output when running and the last one looks like this.
C:\CSC191\Lab\06.recursion>lab6
Enter a postfix expression: 235-*11-/
Invalid divisor.

The problem with that equation is it ends up to be -4/0. I know I could have the function cout the Invalid divisor message but what about the int the function expects to return and also if I put this equation in my program it gets all the way to -4/0 then it hangs up and I can't figure this out. Below is my output. Thanks for any help offered.

This program will take a postfix expression as input, evaluate it, then output the result.

Make selection
1 Evaluate a postfix expression
2 Quit
1
Enter postfix expression: 235-*11-/
eval = 235-*11-/
storing 2 to index 0
eval = 35-*11-/
storing 3 to index 1
eval = 5-*11-/
storing 5 to index 2
eval = -*11-/
should be 3 - 5
replacing 3 at index 1with 8
Array index 1 is -2
index is now 2
eval = *11-/
should be 2 * -2
replacing 2 at index 0with 0
Array index 0 is -4
index is now 1
eval = 11-/
storing 1 to index 1
eval = 1-/
storing 1 to index 2
eval = -/
should be 1 - 1
replacing 1 at index 1with 2
Array index 1 is 0
index is now 2
eval = /
should be -4 / 0
replacing -4 at index 0with -4
Press any key to continue . . .

>I do not understand some of the things you guys are talking about
I was talking about stack, which is in a way, exactly what you have done.
Stacks can be thought of as an array in which the last item which goes in will be the last item which comes out. It is more or less the same thing which you have done.

Regarding your error handling mechanism you have various method:
1.The very best is to use exeptions, They are error handling mechanism of C++. Research about them. Its good to start using them.
2. cout a error and quite the program by using exit(1)[defined under <cstdlib>]. This will cause termination of the program.

I prefer you opt choice 1. and learn about exceptions. After you know about exceptions, you can read the following article about Detecting and responding to division by zero http://www.deitel.com/articles/cplusplus_tutorials/20060325/

Thanks. I will look into exception handling. The only other thing I was thinking to fix this would be to change my return type to a string and output results that way or changing it to a void that just couts everything; although I haven't had a chance to try either yet and I don't know if they would work for recursion. I will look into exception handling then maybe I can make it work without rewriting or substantially modifying the function again.

Returning by string means that you will again have to convert each value you get to integers(although, you can always define a inline function for that like I did). But this was the best method provided exceptions were not invented. Returning by void will be a crime.
Doing things without exception handling will be like following the I-dont-want-to-learn-new-things-but-screw-the-old-one way.
But a slight caution: exceptions are also a good way to make your code unportable in a sense that not most of people(who will study your code) will not catch your exceptions; That bothers you if you were designing a library.
So be sure to issue a exit(1) just after you throw an exception. These thing would make sense when you read about exception handling

Wish you luck!!

I am reading about exceptions right now and have a few questions.
1) I think I understand. For example in my function the part of my switch that handles division would look like.......

``````case '/':
try{
if (b == 0){
throw 0;
}
}
return a / b;``````

now I need to have a catch function

``````catch (int x){
if (x == 0)
cerr<<"Invalid division by zero in equation\n";
}``````

2) Is this correct?
3) Does catch need to be a member of my class or would this be a global thing. (I don't exactly know where to put this in my code.)
4)Do I still need exit(1) somewhere? Ideally I would like it to deliver my error message then return to the menu instead of exiting the program if possible.

also is returning by void a crime because it is bad practice or because it would not work?

Hmm,
>For example in my function the part of my switch that handles division would look like.......
Well, it is not looking good!.
The try block should be in the code which runs your function i.e. the main()
The general layout should be like this

``````{
case '/':
if (b == 0)
{
throw 0;
exit(0);//in case someone don't catch your exception
}
return a / b;
....
...
....
....
}

int main()
{

while (1)
{
try
{
//do all the input output code here,
//
//
break;//this will get you out of the loop if no exception is thrown
}
catch (int i)
{
if (i==0)
cout<<"Error! div by zero";
}
//flow returns here when a exception is thrown
//thus get back to the start of the loop again
}//ending while(1)

}``````

>Does catch need to be a member of my class or would this be a global thing. (I don't exactly know where to put this in my code.)
catch{} is a global thing, should be put just after the try{} block

>Do I still need exit(1) somewhere? Ideally I would like it to deliver my error message then return to the menu instead of exiting the program if possible.
Use exit(1) just after you throw the exception. This will ensure that your program at least terminates(rather than screwing your machine resources) if the exception has not been handled. Although, my compiler (g++)r print a error message if the exceptions are thrown but not catched. But then, it is implementation dependent. So it is better to put a exit(1);

>also is returning by void a crime because it is bad practice or because it would >not work?
I exclaimed that it is a crime in your case as it would imply that you will have to cout everything in the evaluative function, which is bad.

Yes, the code segment I gave will do exactly the same thing. Lets see how:
If the exception is not encountered any function inside the try block, the program will eventually meet the break; statement and thus the outer while loop will terminate. If the exception is catched, the program flow returns to the end of the catch{} block hence the Loop starts again.

Thanks for all your help. It is appreciated. I am looking over you post to see if my code can still be improved, but I actually came back here to post that I had figured how how to make this work in a bit of a convoluted way. It does use an exception though. I also added a bool bad_divisor variable to my class that main() uses to determine whether or not to show the results of function. I am pasting code below. As I said it does fully work but I am still open to suggestions that may make it better or more efficient. Thanks again for all you help:)

``````# include <iostream>
# include <string>
using namespace std;

# define MAX_SIZE 50

class Calculator{
public:
Calculator(); // default constructor
int postfix(string s); // recursive function for evaluating postfix equations
bool get_bad_divisor(); // Check to see if eq had division by 0
void reset_bad_divisor(); // resets bad_divisor flag after each eq for next one
private:
int index; // Keeps current place of last stored number in array
int the_array[MAX_SIZE]; //Array for storing ints from equation until operator is found
bool bad_divisor; // Flag to check if eq had Division by 0
};

int main(){
Calculator eval; // Insatnce of Calculator Class
bool quit = false; // When set to true stops menu loop
string pf_eq = ""; // input string for equation
cout<<"This program will take a postfix expression as input, evaluate it, then output the result.\n";
cout<<"\nMake selection\n";
cout<<"1 Evaluate a postfix expression\n";
cout<<"2 Quit\n";
cin>>choice;

switch (choice){ // Handle User selection
case 1: // evaluate a postfix eq
cout<<"Enter postfix expression: ";
cin.clear();
cin>>pf_eq;
} else {
}
break;
case 2: // quit program
cout<<"Thanks for using the postfix evaluation program!\n";
quit = true;
break;
default: // Invalid menu choice input
}
} while (!quit); // End Menu Loop

}

Calculator::Calculator(){ // default constructor
index = 0; // Set index to 0
}
bool Calculator::get_bad_divisor(){ // Check to see if eq had division by 0
}
void Calculator::reset_bad_divisor(){ // resets bad_divisor flag after each eq for next one
}

int Calculator::postfix(string s){ // recursive function for evaluating postfix equations
//cout<<"eval = "<<s<<endl; // Debug cout
int a, b; // Variables for the two ints currently being operated on
if (s.length() == 0 ){
index = 0;
return the_array[0];
} else if (isdigit(s[0])){
//cout<<"storing "<<s[0]<<" to index "<<index<<endl;  // Debug cout
the_array[index] = s[0]-48;
index++;
return postfix(s.substr(1,s.length()-1));
} else {
a = the_array[index-2]; // Get last 2 stored digits
b = the_array[index-1]; // Get last 2 stored digits
switch (s[0]) {

case '+':
//cout<<" should be "<<a<<" "<<s[0]<<" "<<b<<endl; // Debug cout
//cout<<"replacing "<<the_array[index-2]<<" at index "<<index-2<<"with "<<a + b<<endl; // Debug cout
the_array[index-2] = a + b; // Perform operation and store result in index of a
//cout<<"Array index "<<index-2<<" is "<<the_array[index-2]<<endl; // Debug cout
break;

// Subtraction operator
case '-':
//cout<<" should be "<<a<<" "<<s[0]<<" "<<b<<endl; // Debug cout
//cout<<"replacing "<<the_array[index-2]<<" at index "<<index-2<<"with "<<a - b<<endl; // Debug cout
the_array[index-2] = a - b; // Perform operation and store result in index of a
//cout<<"Array index "<<index-2<<" is "<<the_array[index-2]<<endl; // Debug cout
break;

// Multiplication operator
case '*':
//cout<<" should be "<<a<<" "<<s[0]<<" "<<b<<endl; // Debug cout
//cout<<"replacing "<<the_array[index-2]<<" at index "<<index-2<<"with "<<a * b<<endl; // Debug cout
the_array[index-2] = a * b; // Perform operation and store result in index of a
//cout<<"Array index "<<index-2<<" is "<<the_array[index-2]<<endl; // Debug cout
break;

// Division operator
case '/':
//cout<<" should be "<<a<<" "<<s[0]<<" "<<b<<endl; // Debug cout
//cout<<"replacing "<<the_array[index-2]<<" at index "<<index-2<<"with "<<a / b<<endl; // Debug cout
//if (b == 0)
//	cout<<"Equation contains illegal division by 0. This Program will now crash and burn!!!!!!!!!!!!\n"; // invalid division by 0
try {
if (b == 0){
throw 0;
} else {
the_array[index-2] = a / b; // Perform operation and store result in index of a
}
}
catch (int x){
if (x == 0)
cerr<<"Equation contains illegal division by 0.\n";
}
//the_array[index-2] = a / b; // Perform operation and store result in index of a
//cout<<"Array index "<<index-2<<" is "<<the_array[index-2]<<endl; // Debug cout
break;
default :
}
index = index-1;
//cout<<"index is now "<<index<<endl; // Debug cout
return postfix(s.substr(1,s.length()-1));
}
return the_array[0];
}``````

>It does use an exception though.
But it is not using the way it should. I guess my last post was of no use.
Do you know why exceptions were invented? To avoid checking the return value of each function for errors. And look what you are doing. You are still checking `if(eval.get_bad_divisor())` in you main().So what is the point in using exceptions. And moreover, you are using the try-catch block inside the definition of a function that throws the exception.
I think you should read my last post again.
Well, I don't mind if you use the old return-value check approach, but then, please don't use (flawed) exception handling mechanism for just the sake of using it.

Another point: dont use #define MAX_SIZE 50
use `const int MAX_SIZE=50;` instead. Here is why:http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.7

I hope you understand my point about exceptions. Here is a good tut for you:http://www.ozzu.com/cpp-tutorials/tutorial-exceptions-t86515.html

Ok, I am rather guilty, fine?
So, I think I would need to explain it further.
Look, You should throw an exception whenever you encounter a error in any piece of your code by using `throw anumber` whenever you encounter a error. But, use the try-catch block in the calling code of the function. Not when throwing exception. Getting it?
In short, you should write the try-catch block in main() and not in postfix(). Got it?
You should issue a throw 0 in postfix but catch it in main()
Phew!

That makes some sense but I thought the catch needed to be placed just after the try in the code.

>That makes some sense but I thought the catch needed to be placed just after the >try in the code.
Yes you are right. So that what I said:

``````.
.
.
{//in post fix
if (somecondition)
throw 0;//look, i hv not used any try{}
.
.
.
}//end of postfix

int main()
{
while (1)
{
try//here i use try
{
//somecode
postfix();
break;
}
catch (int i)//and catch just after try{}
{
if (i==0)
cout<<"Erorror";
}
}
}``````

Okay I see. I thought the throw had to come from inside a try. I did not realize it could be used elsewhere. then in main() it looks something like this....

``````case 1: // evaluate a postfix eq
cout<<"Enter postfix expression: ";
cin.clear();
cin>>pf_eq;
try{
throw 1;
} else {
}
catch (int q){
if (q == 1){
cout<<"Invalid division by 0 in expression!\n";
}
}
break;``````

Better, but Still not got it!
No problem. I will try to explain again:
See, the whole story of exception is to eradicate the need for checking anything in main() as you are doing

``````try{
throw 1;
} else {
}``````

So now, you have already thrown a exception while dealing with postfix(), right?
I mean, you have already thrown the exception in the postfix() function, so you don't need to throw it again in main()[and neither there is need to check `if (eval.get_bad_divisor())` ]
First of all, try{} block should contain all those function call which can potentially throw an exception. In your case it is postfix(). So you should include the postfix() in the try block. Now the code should appear like this:

``````case 1: // evaluate a postfix eq
cout<<"Enter postfix expression: ";
cin.clear();
cin>>pf_eq;
try{
}
catch (int q){
if (q == 1){
cout<<"Invalid division by !\n";
}
}
break;

}``````

Lets see what will happen in the above code:
You are calling postfix() in a try block, right? So, either two things can happen:
1.The postfix() don't encounter any div-zero error: In this case, no exception will be thrown by postfix() hence the try block will be executed fully and the control will return directly to Line13 (overlooking the catch{})
2.If postfix() emits a exception, the control will be (no matter where it was earlier) directly passed to the catch block at Line9 and will issue a error and continue from Line13

After Line13, your program will run as usual. So no need of the ugly eval.get_bad_divisor()

Got it?

Or after giving it a little more thought inside postfix() should look like this

``````case '/':
if (b == 0){
throw 0;
} else {
the_array[index-2] = a / b; // Perform operation and store result in index of a
}
break;``````

and main should look like this...

``````case 1: // evaluate a postfix eq
cout<<"Enter postfix expression: ";
cin.clear();
cin>>pf_eq;
try{
}
catch (int q){
if (q == 0){ // Catch receives 0 thrown from postfix
result = false;// bool variable no longer needed in class now using local variable in main()
}
}
if (!result){
cout<<"Invlaid division by 0 in expression!\n";
} else {
}
break;``````

Sorry I think we were both working on replies at the same time. Looking over yours now.

and main should look like this...

The `answer = eval.postfix(pf_eq);` has been duplicated, once outside try and one inside. Use the inside one and remove the outside one like this:

``````cin>>pf_eq;
try{
``````

DO the modification and tell me.

PS: use "(code=c++)(/code)" instead of "(CODE)(/CODE)"

Sorry that was a copy and paste error. I actually only meant for the one inside. I haven't had a chance to compile these changes yet. I am at work and can you believe they expect me to do things here too:'( Anyway I should get a chance to try it in the next hour or so. Does that code look better though?
PS: I can use the other tags no problem:)

Yes, the last code you posted rocks! but again a few problems are there.
1. The catch{} should cout the error instread of setting a bool and again checking for a if (remember, the whole moto was to eradicate if's)
2. Remember, that you can always embed the `cout<<pf_eq<<" = "<<answer<<".\n";` in the try{} block after the call to postfix()
In this way, you will automatically get the answer if no exceptions are thrown or you will get a error in case of exception(note that the `cout<<pf_eq<<" = "<<answer<<".\n";` wont be executed once the exception is thrown)

I kept the bool and left the cout on the outside because I don't want it to cout anything but the error msg if it gets thrown. If I move the cout inside wouldn't it still be output before the catch does it's job?