[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Read a postfix expression and display value using STACKS

Posted on 2011-05-10
4
Medium Priority
?
298 Views
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?

thanks.

INPUTS:
enter values: 7 4 8 2
enter postfix values: ab*abcd+*++$
#include<iostream>
#include<cctype>

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;

	p.ClearStack();
	q.ClearStack();

	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: ";
	cin>>a>>b>>c>>d;

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

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

Open in new window

0
Comment
Question by:pgmerLA
  • 2
  • 2
4 Comments
 
LVL 53

Accepted Solution

by:
Infinity08 earned 2000 total points
ID: 35726968
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 :

        ab*abcd+*++$
        ababcd*+*++$
        ab*a+b*c+d+$

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.
0
 
LVL 8

Expert Comment

by:lomo74
ID: 35738092
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
		}
		pexpr++;
	}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 35738097
>> you have to read the expression into a buffer, then scan the buffer.

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

Expert Comment

by:lomo74
ID: 35738325
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 >> ...
0

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
Suggested Courses

834 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