Infix to Postfix help

[Marissak]

The question I'm trying to answer is:
Write an object oriented C++ program to translate an infix expression to postfix.

I have done much of it but after I debug the only output is "Postfix:" and I cannot figure out why.

This is my code so far:

#include <iostream>
#include <string>
#include <stack>
#include <sstream>

using namespace std;

template<class T>
class Stack : public stack<T> {
public:
    T pop() {
        T tmp = top();
        stack<T>::pop();
        return tmp;
    }
};

class inToPost {
public:
    void fix();
    int prec(string);
private:
    Stack<string> stack;
};

void inToPost::fix() {
    cout << "Enter an equation with no spaces." << endl;
    cout << "For example: " << endl;
    cout << "4*8+9(2-3)" << endl;

    string line, str;
    cin >> line;
    getline(cin, line);
    istringstream iss(line);
    cout << "Postfix: " << endl;
    while(!iss.eof()){
        iss >> str;
        if(str != "+" && str != "-" && str!= "/" && str != "*" && str != "(" && str != ")") {
            cout << str; //While the input is none of the operators, output the variable
        }
        else if(str == ")") { //If the ) is encountered, pop the stack until the ( is found
            while(str != "(") {
                cout << stack.pop();
            }
            stack.pop(); //Then disregard the ( and )
        }
        else { 
            int x = prec(str); //Find the precendence
            if(x > prec(stack.top())) { //If it's higher than the top element on the stack
                stack.push(str); //Push the element onto the stack
            }
            else if(x <= prec(stack.top())) { //If it's lower
                cout << stack.pop(); //Pop the top of the stack

            }
        }
    }
    while(!stack.empty()) {
            cout << stack.pop();
    }   
}

int inToPost::prec(string str) { //Determines the precedence of the operator
    if(str == "^") {
        return 5;
    }
    else if(str == "/" || str == "*") {
        return 4;
    }
    else if(str == "+" || "-") {
        return 3;
    }
    else
        return 0;
}

int main() {
    inToPost().fix();

    return 0;

}

[SgtMe]

Please repost your code with code tags (push the code button before you paste your code).

[Marissak]

I apologize, I am new to the site.

#include <iostream>
#include <string>
#include <stack>
#include <sstream>

using namespace std;

template<class T>
class Stack : public stack<T> {
public:
    T pop() {
        T tmp = top();
        stack<T>::pop();
        return tmp;
    }
};

class inToPost {
public:
	void fix();
	int prec(string);
private:
	Stack<string> stack;
};

void inToPost::fix() {
	cout << "Enter an equation with no spaces." << endl;
	cout << "For example: " << endl;
	cout << "4*8+9(2-3)" << endl;

	string line, str;
	cin >> line;
	getline(cin, line);
	istringstream iss(line);
	cout << "Postfix: " << endl;
	//while(!iss.eof()){
	while(iss >> str) {
		//iss >> str;
		if(str != "+" && str != "-" && str!= "/" && str != "*" && str != "(" && str != ")") {
			cout << str; //While the input is none of the operators, output the variable
		}
		else if(str == ")") { //If the ) is encountered, pop the stack until the ( is found
			while(str != "(") {
				cout << stack.pop();
			}
			stack.pop(); //Then disregard the ( and )
		}
		else { 
			int x = prec(str); //Find the precendence
			if(x > prec(stack.top())) { //If it's higher than the top element on the stack
				stack.push(str); //Push the element onto the stack
			}
			else if(x <= prec(stack.top())) { //If it's lower
				cout << stack.pop(); //Pop the top of the stack

			}
		}
	}
	while(!stack.empty()) {
			cout << stack.pop();
	}	
}

int inToPost::prec(string str) { //Determines the precedence of the operator
	if(str == "^") {
		return 5;
	}
	else if(str == "/" || str == "*") {
		return 4;
	}
	else if(str == "+" || "-") {
		return 3;
	}
	else
		return 0;
}

int main() {
	inToPost().fix();

	return 0;

}

[SgtMe]

Don't worry it's cool :) The point is that you now know :)

[StuXYZ]

First off welcome Daniweb.

Next, now that I have your code, what are the problems with it. Unfortunately, quite a few -- I have listed a few to get you going in the right direction.

The first is that you are using this code [lines 32-34]:

cin >> line;            // get a string into line up to the first space deliminter ] 
getline(cin, line);     // This reads the rest of the line 
istringstream iss(line);

That means that for the program to accept say 4*5 you have to enter: someJunk 4*5 . All the characters in the first expression up to the space ("someJunk") are thrown away.

So fix it by removing the cin>>line; Unfortunately, that isn't your only problem:

while(iss >> str) 
  {
    // Stuff...
  }

Since str is a string [not a char] then it assumes that you are entering you text like this: 5 * 4 + ( 6 - 32 ) .

The obvious way round that is to use a char. There are a lot of changes to that, you need to make the "+" into single character e.g. '+' .

Next you are using a very strange construct for handling the brackets

else if(str == ")") 
  {   //If the ) is encountered, pop the stack until the ( is found
    while(str != "(") 
      {
        // THIS LINE doesn't change the str so it is an infinite loop:
        // Until stack thows an exception.
	cout << stack.pop();
      }

Can I say, that IF you put using namespace std; at the top of your code [Something I think nobody should do]. The use Stack as a class derived from stack and a variable stack, which is an instance of Stack, you are going to make a mistake and the compiler error messages are going to be incomprehensible or it is going to be a runtime error.

Next, can you use a few references, e.g. int prec(string str) which calculates the precedence could better be (a) private and int prec(const std::string&) const .
Note: you have written this: else if(str == "+" || "-") That will compile BUT it will not do what you want.

That error and the error in Stack,

T tmp = top();         // THIS is depreciated: use T tmp = stack<T>::top();
  stack<T>::pop();
  return tmp;

Tells me that you are not compiling with warnings on. The compiler is your friend it is trying to help! Please listen to it!!!.

Anyway, fix some of those problems, and do a little testing, then post back what you have and we will have another look.

Hope that helps.

[Marissak]

I basically fixed the things you said - I agreed with them because I made careless mistakes.
For

T tmp = top();
  stack<T>::pop();
  return tmp;

that is how it is in the book and that is how my teacher always does it. It is like that in all of my other programs as well.

So this is what it looks like now: (It's basically the same)

#include <iostream>
#include <string>
#include <stack>
#include <sstream>

using namespace std;

template<class T>
class Stack : public stack<T> {
public:
    T pop() {
        T tmp = top();
        stack<T>::pop();
        return tmp;
    }
};

class inToPost {
public:
	void fix();
	int prec(string);
private:
	Stack<string> stack;
};

void inToPost::fix() {
	cout << "Enter an equation with no spaces." << endl;
	cout << "For example: " << endl;
	cout << "4*8+9(2-3)" << endl;

	string line, str;
	getline(cin, line);
	istringstream iss(line);
	cout << "Postfix: " << endl;
	//while(!iss.eof()){
	while(iss >> str) {
		//iss >> str;
		if(str != "+" && str != "-" && str!= "/" && str != "*" && str != "(" && str != ")") {
			cout << str; //While the input is none of the operators, output the variable
		}
		else if(str == ")") { //If the ) is encountered, pop the stack until the ( is found
			while(str != "(") {
				str = stack.pop();
				cout << str;
			}
			stack.pop(); //Then disregard the ( and )
		}
		else { 
			int x = prec(str); //Find the precendence
			if(x > prec(stack.top())) { //If it's higher than the top element on the stack
				stack.push(str); //Push the element onto the stack
			}
			else if(x <= prec(stack.top())) { //If it's lower
				cout << stack.pop(); //Pop the top of the stack

			}
		}
	}
	while(!stack.empty()) {
			cout << stack.pop();
	}	
}

int inToPost::prec(string str) { //Determines the precedence of the operator
	if(str == "^") {
		return 5;
	}
	else if(str == "/" || str == "*") {
		return 4;
	}
	else if(str == "+" || str == "-") {
		return 3;
	}
	else
		return 0;
}

int main() {
	inToPost().fix();

	return 0;

}

but the problem I'm having now is that it prints out the equation. Like if I enter 4+3-5*2 then it outputs Postfix: 4+3-5*2
I know it is because it takes it to be one string instead of each character separately. But I cannot figure out how to fix it.

[Marissak]

I also tried changing all of the strings to char and it basically made it worse.

[StuXYZ]

The first thing you need to do to fix this, is to realize that you are passing WHOLE strings and not individual characters:
Add this line like this:

while(iss >> str) 
    {
      std::cout<<"str::"<<str<<"::"<<std::endl;        // ADD THIS LINE
      //iss >> str;

That will show you that you have str that is a complete string, it is not individual characters. E.g. When you do the test str!="+" it will ALWAYS be true, since "4+3" is absolutely NOT "+". Thus your code simply think you have a single object, and the postfix and prefix versions of a single object/number are both the same, just the object.

When you put str to be an individual character (e.g. char). You got a whole pile of errors. THAT IS GOOD!!!! That is the compiler helping you fix your code that is simple wrong in many places.

So, in short, make str (a) a char , (b) a better name, that you are not going to mistype and find is a keyword. (c) fix all of the compiler errors and then try a little debugging, e.g. putting output statement and assert's etc.

Sorry that is a little harsh but that is the only way you are going to fix this code that I can see. When you have fixed the compiler errors, feel free to repost, I/others will happily help with the remaining runtime bugs.

Finally, about putting a qualifier on on the line T tmp = stack<T>::top(); . (line 12 of your code) the C++ standard, section 14.3 say that you must.
The following FAQ entry says what happens if you don't AND you compiler tries to guess [instance of when it guesses wrong!] http://www.parashift.com/c++-faq-lite/templates.html#faq-35.19 There is much further discussion on the web, but the three compilers I use (g++, portland, and IBM) all accept it with a permissive flag or a warning. Since neither are desirable, it is better to just fix the issue. Note, you can qualify it with either a full name, as I have done above, or a pointer this->top() , as you wish.

[Marissak]

I apologize for not seeing that in the beginning. I do see it now. I've changed my code around a bit and I have gotten it to output, but I do not think it is in the correct order.

Here is my updated code:

#include <iostream>
#include <string>
#include <stack>
#include <sstream>

using namespace std;

template<class T>
class Stack : public stack<T> {
public:
    T pop() {
        T tmp = top();
        stack<T>::pop();
        return tmp;
    }
};

class inToPost {
public:
	void fix();
	int prec(char);
private:
	Stack<char> stack;
};

void inToPost::fix() {
	cout << "Enter an equation with no spaces." << endl;
	cout << "For example: " << endl;
	cout << "4*8+9(2-3)" << endl;

	string line;
	char str;
	int x = 0;
	getline(cin, line);
	istringstream iss(line);
	cout << "Postfix: " << endl;
	while(iss >> str) {
		if(str != '+' && str != '-' && str!= '/' && str != '*' && str != '(' && str != ')') {
			cout << str; //While the input is none of the operators, output the variable
		}
		else if(str == ')') { //If the ) is encountered, pop the stack until the ( is found
			while(!stack.empty() && stack.top() != '(') {
				cout << stack.pop();
			}
			if(!stack.empty()) {
				stack.pop(); //Then disregard the ( and )
			}
		}
		else if(str == '+' || str == '-' || str == '/' || str == '*'){ 
			while(!stack.empty() && stack.top()!='(') {
				if(prec(stack.top()) >= prec(str)) {//If the prec of the top of stack
					cout << stack.pop();	//is bigger than the prec of the char
				}							//pop the stack and output it;
				else if(prec(stack.top()) < prec(str)) {//If it is smaller, break;
					break;
				}
			}
			stack.push(str); //push the char onto the stack
		}
	}
	while(!stack.empty()) { //while the stack is not empty
			cout << stack.pop(); //pop the rest of the stack;
	}	
}

int inToPost::prec(char str) { //Determines the precedence of the operator
	if(str == '/' || str == '*') {
		return 4;
	}
	else if(str == '+' || str == '-') {
		return 3;
	}
	else
		return 0;
}

int main() {
	inToPost().fix();

	return 0;

}

I know that the reason it is not outputting correctly is directly related to this section:

else if(str == '+' || str == '-' || str == '/' || str == '*'){ 
			while(!stack.empty() && stack.top()!='(') {
				if(prec(stack.top()) >= prec(str)) {//If the prec of the top of stack
					cout << stack.pop();	//is bigger than the prec of the char
				}							//pop the stack and output it;
				else if(prec(stack.top()) < prec(str)) {//If it is smaller, break;
					break;
				}
			}
			stack.push(str); //push the char onto the stack
		}

but I'm not exactly sure how to fix it

[Marissak]

After going through with the debugger I finally got it! I realized I was missing one little essential statement. Thank you for all your help!:)

[GouseKSyed]

If you want to code for Infix to Postfix and evaluation of postfix contact me i have the solution. you can mail me @[e-mail]