8 Replies - 1858 Views - Last Post: 18 July 2012 - 03:53 PM Rate Topic: -----

#1 MitulP91  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 18-July 12

Evaluating a postfix expression

Posted 18 July 2012 - 02:30 PM

Hey everyone. I am currently attempting to create a program that will calculate postfix expressions using stacks. The code I currently have is as follows:

#include <iostream>
#include <stack>	
#include <string>	
#include <cctype>	

using namespace std;

int main()
{
    int i;
    string expression;
    char token;
    int value, value1, value2;
    stack<char> myStack;

	cout << "Please enter the RPN expression to be evaluated: " << endl <<
		"(Note: Each digit or operator should be separated by a space, and end with :)/>"
		<< ": " << endl;
		
	getline(cin, expression);
  
    i = 0;
    token = expression[i];
    while((i < expression.size()) && (token != '='))
		{
			if (isdigit(token))
				{
			value = token - '0';
                    myStack.push(value);
                }
            
			else
                {
                    value2 = myStack.top();
                    myStack.pop();
                    value1 = myStack.top();
                    myStack.pop();
                    switch(token)
						{
							case '+': value = value1 + value2;
                                      break;
                            case '-': value = value1 - value2;
                                      break;
                            case '*': value = value1*value2;
                                      break;
                            case '/': value = value1/value2;
                                      break;
                        }
                    myStack.push(value);
                 }
          i++;
          token = expression[i];
		}
    value = myStack.top();
    myStack.pop();
    cout << expression << " " << value << endl;
	cout << endl;

	return 0;
}



Sorry I posted it by mistake before I could ask my question. When I build it comes up fine however when I attempt to debug it the error "deque iterator not deferencable" keeps appearing. I've tried looking this up but can't find anything conclusive as to why this issue is occurring. Help would be much appreciated.

Also I'm not sure why it appears that way in the code I posted, but everywhere it says
exp<b></b>ression is meant to be the variable string expression.

Is This A Good Question/Topic? 0
  • +

Replies To: Evaluating a postfix expression

#2 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3454
  • View blog
  • Posts: 10,661
  • Joined: 05-May 12

Re: Evaluating a postfix expression

Posted 18 July 2012 - 03:02 PM

Oops... wrong tab...

This post has been edited by Skydiver: 18 July 2012 - 03:05 PM

Was This Post Helpful? 0
  • +
  • -

#3 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3454
  • View blog
  • Posts: 10,661
  • Joined: 05-May 12

Re: Evaluating a postfix expression

Posted 18 July 2012 - 03:14 PM

Have you stepped through your program with a debugger? If not, I think that you will find lines 34-49 very interesting when the user follows your instruction of using a space to separate digits or operators.

In this case, I don't think it's user error. :lol:

Also ending the expression with ":)" seems to conflict with your while loop condition.

This post has been edited by Skydiver: 18 July 2012 - 03:15 PM

Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is offline

  • member icon


Reputation: 3988
  • View blog
  • Posts: 12,301
  • Joined: 25-December 09

Re: Evaluating a postfix expression

Posted 18 July 2012 - 03:21 PM

Quote

exp<b></b>ression is meant to be the variable string expression.

This is a problem with the board software but thanks for catching the problem.

What compiler are you using?

Please show an complete example of your input.

It looks like you are trying to pop something off an empty stack.

Jim
Was This Post Helpful? 0
  • +
  • -

#5 MitulP91  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 18-July 12

Re: Evaluating a postfix expression

Posted 18 July 2012 - 03:26 PM

I'm not sure I understand how to fix the issue. This is an assignment I have to complete and I've been instructed to place spaces between all the inputted numbers and operators and to place a : at the end of the expression.

How would I go about altering the program to allow this?

View Postjimblumberg, on 18 July 2012 - 03:21 PM, said:

Quote

exp<b></b>ression is meant to be the variable string expression.

This is a problem with the board software but thanks for catching the problem.

What compiler are you using?

Please show an complete example of your input.

It looks like you are trying to pop something off an empty stack.

Jim


I am using Visual Studio C++ 2010 Express. An example input given to me is as follows:

Please enter the RPN expression to be evaluated:

9 2 1 + / 4 * :
Token = 9 Push 9
Token = 2 Push 2
Token = 1 Push 1
Token = + Pop 1 Pop 2 Push 3
Token = / Pop 3 Pop 9 Push 3
Token = 4 Push 4
Token = * Pop 4 Pop 3 Push 12
Token = Pop 12
type 'Y' or 'y' to continue or type any other letter to quit: y
Was This Post Helpful? 0
  • +
  • -

#6 jared.deckard  Icon User is offline

  • New D.I.C Head

Reputation: 18
  • View blog
  • Posts: 46
  • Joined: 11-July 12

Re: Evaluating a postfix expression

Posted 18 July 2012 - 03:45 PM

http://ideone.com/7htsg
#include <iostream>
#include <stack>	
#include <string>	
#include <cctype>	

using namespace std;

int main()
{
	int i;
	char inputEx[128];
	char token;
	int value, value1, value2;
	stack<char> myStack;

	cout << "Please enter the RPN inputEx to be evaluated: " << endl <<
		"(Note: Input must end with an equals sign (=))"
		<< ": " << endl;
		
	cin.getline(inputEx, 128);
  
	i = 0;
	
	for(i=0; inputEx[i]!='='; i++)
	{
		token = inputEx[i];
		
		if(token == ' ') continue;
		
		if (isdigit(token))
		{
			value = token - '0';
			myStack.push(value);
		}
		else
		{
			value2 = myStack.top();
			myStack.pop();
			value1 = myStack.top();
			myStack.pop();
			switch(token)
			{
				case '+': value = value1 + value2;
				break;
				case '-': value = value1 - value2;
				break;
				case '*': value = value1*value2;
				break;
				case '/': value = value1/value2;
				break;
			}
			myStack.push(value);
		}
	}
	
	value = myStack.top();
	myStack.pop();
	
	cout << inputEx << " " << value << endl;
	cout << endl;
	
	return 0;
}



You must skip over the logic in the for loop if spaces are encountered.

Check to see if there are enough elements in the stack before doing each operation. If there are not, the expression is invalid. Once the loop is finished the stack should only contain one value. If it does not the expression was invalid.

This post has been edited by jared.deckard: 18 July 2012 - 03:57 PM

Was This Post Helpful? 0
  • +
  • -

#7 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3454
  • View blog
  • Posts: 10,661
  • Joined: 05-May 12

Re: Evaluating a postfix expression

Posted 18 July 2012 - 03:45 PM

Quote

This is an assignment I have to complete and I've been instructed to place spaces between all the inputted numbers and operators and to place a : at the end of the expression.


If the ':' is the expression terminator, why are you looking for '=' on line 24? Is this code you got somewhere else? It's okay, we won't tell your teacher. :lol:

Quote

I'm not sure I understand how to fix the issue.


Well right now your code logic looks like:
while(input is not '=')
{
   if input is a digit
       handle digit
   else
       handle operator
}



Your else clause is a catch all for everything that is not a digit. And your handle operator code assumes that it will get an operator so it preemptively pops things off the stack, but never puts it back in if it wasn't an operator.

Why not add another condition:
if input is digit
    handle digit
else if input is space
    handle space
else
    handle operators


Was This Post Helpful? 0
  • +
  • -

#8 jimblumberg  Icon User is offline

  • member icon


Reputation: 3988
  • View blog
  • Posts: 12,301
  • Joined: 25-December 09

Re: Evaluating a postfix expression

Posted 18 July 2012 - 03:46 PM

Since you are using a space to separate your values you need to skip any processing and just increment your index.

Jim
Was This Post Helpful? 0
  • +
  • -

#9 MitulP91  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 64
  • Joined: 18-July 12

Re: Evaluating a postfix expression

Posted 18 July 2012 - 03:53 PM

Thanks for all the help guys. I'm gonna work on everything you said and see what I can figure out. And yes I looked to another forum post for some ideas as to how to do the assignment.

Appreciate all the help!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1