Read a postfix expression and display value using STACKS

Posted on 2011-05-10
Last Modified: 2012-06-21
Hi, I have to read in a  postfix expression and find its final value.
my answer is way wrong. the correct answer is 75. I get garbage.
can you please tell me how to fix my code?


enter values: 7 4 8 2
enter postfix values: ab*abcd+*++$

using namespace std;

template<class T, int n>
class Stack
{private: T x[n];int counter;
public: void ClearStack(){counter =0;}
		bool EmptyStack(){if(counter ==0) return true;
		else return false;}
		bool FullStack(){if(counter ==n) return true;
		else return false;}
		void Push(T a){x[counter]=a; ++counter;}
		T Pop(){counter--; return x[counter];}


int main(){
	Stack <char, 80> p;
	Stack <int, 80> q;


	int a=0,b=0,c=0,d=0,res=0,x=0,y=0;
	char ch,ch1;

	cout<<"Enter values for a, b, c, d: ";

	cout<<"Enter the postfix expression: ";
	while(cin.get(ch),ch !='$')
			{case 'a': q.Push(a);break;
			case 'b': q.Push(b);break;
	else p.Push(ch);}

	x=q.Pop(); y=q.Pop();
		{case '*': res=x*y;q.Push(res);break;
		case'+':res=x+y; q.Push(res);break;
	cout<<x;//I get garbage
	//OR i type: cout<< res; and I get a too large number
return 0;}

Open in new window

Question by:pgmerLA
    LVL 53

    Accepted Solution

    You cannot just split the input into two stacks like that.

    The problem is that there is no way to distinguish between different inputs. For example for the following inputs, your current code would give the exact same result - even though they're quite different :


    You need to keep the operators (+, *) and operands (a, b, c, d) in the order that they were given as input. So, you need to keep everything in one stack.

    The easiest way to process postfix expressions, is to actually perform the calculations WHILE you read the input :

    You read a character in a loop. There are two possibilities :
    (a) if it's an operand, push it on the stack
    (b) if it's an operator, pop two operands from the stack, apply the operator to them, and push the result back on the stack.

    When all input is read, the stack should contain just one value (assuming the input was a valid postfix expression) : the final result.
    LVL 8

    Expert Comment

    Infinity08 is correct.
    Moreover, you have to read the expression into a buffer, then scan the buffer.

    ////Stack <char, 80> p; REMOVE this
    	char expr[256];
    	char *pexpr = expr;
    	cout << "Enter the postfix expression: ";
    	cin >> expr;
    	while (*pexpr && *pexpr != '$') {
    		if (isalpha(*pexpr)) {
    			... //push a, b, c or d on q
    		} else {
    			... //pop x, y; push operation result on q

    Open in new window

    LVL 53

    Expert Comment

    >> you have to read the expression into a buffer, then scan the buffer.

    No, you don't need to. You can.
    LVL 8

    Expert Comment

    well, right, you don't need to, you can.
    if you don't, you have to deal with the extra '\n' coming in from the previous cin >> a >> b >> ...

    Featured Post

    Better Security Awareness With Threat Intelligence

    See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

    Join & Write a Comment

    Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
    Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
    The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
    The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

    754 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    24 Experts available now in Live!

    Get 1:1 Help Now