10 Replies - 10504 Views - Last Post: 05 April 2008 - 07:12 PM Rate Topic: -----

#1 C++++  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 03-November 07

Infix to Postfix

Posted 04 November 2007 - 02:59 PM

please help

i have a code let you calculate a fully parenthesized arithmetic expression only (with bracket)

my question is : how can I calculate it without bracket

for example:
((12-2)*(9/3))
if we put it as privious way we shall get 30

but if I put it as
12-2*9/3
it will gives different answer

how can i solve this problem

my code :

// written by C++++ from www.dreamincode.net

#include <cctype>	 
#include <cstdlib>	
#include <cstring>	
#include <iostream>   
#include <stack>	  
using namespace std;


double read_and_evaluate(istream& ins);
void evaluate_stack_tops(stack<double>& numbers, stack<char>& operations);

int main( )
{
	double answer;

	cout << "Type a fully parenthesized arithmetic expression:" << endl;
	answer = read_and_evaluate(cin);
	cout << "That evaluates to " << answer << endl;

	return EXIT_SUCCESS;
}


double read_and_evaluate(istream& ins)
{
	const char DECIMAL = '.';
	const char RIGHT_PARENTHESIS = ')';

	stack<double> numbers;
	stack<char> operations;
	double number;
	char symbol;
	
	while (ins && ins.peek( ) != '\n')
	{
		if (isdigit(ins.peek( )) || (ins.peek( ) == DECIMAL))
		{
			ins >> number;
			numbers.push(number);
		}
		else if (strchr("+-*/", ins.peek( )) != NULL)
		{
			ins >> symbol;
			operations.push(symbol);
		}
		else if (ins.peek( ) == RIGHT_PARENTHESIS)
		{
			ins.ignore( );
			evaluate_stack_tops(numbers, operations);
		}
		else
			ins.ignore( );
	}

	return numbers.top( );
}

void evaluate_stack_tops(stack<double>& numbers, stack<char>& operations)
{
	double operand1, operand2;

	operand2 = numbers.top( );
	numbers.pop( );
	operand1 = numbers.top( );
	numbers.pop( );
	switch (operations.top( ))
	{
		case '+': numbers.push(operand1 + operand2);
				  break;
		case '-': numbers.push(operand1 - operand2);
				  break;
		case '*': numbers.push(operand1 * operand2);
				  break;
		case '/': numbers.push(operand1 / operand2);
				  break;
	}
	operations.pop( );
}



Edit: Please use :code: when writing your code. Thanks! :)

This post has been edited by Martyr2: 04 November 2007 - 04:30 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Infix to Postfix

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Infix to Postfix

Posted 04 November 2007 - 04:37 PM

Well, there is a slight problem: ((12-2)*(9/3)) and 12-2*9/3 are very different expression that evaluate to very different answers... The fist one is 10*3 and should be 30... the second is 12-6=6... if you want to make it so that they both evaluate to the same value you will need to break your program so that it does not properly evaluate expressions...

Now if you mean that the first expression evaluates properly, but the second does not... Well then what you need to do is think about operator precedence.
Was This Post Helpful? 0
  • +
  • -

#3 C++++  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 03-November 07

Re: Infix to Postfix

Posted 04 November 2007 - 05:02 PM

thanks for reply ,
but my question how can i let 12-2*9/3 gives the correct answer ?
i want it to give me answer same as your answer (in calculation by changing in the code)

we can say the program gives priority for *&/ at first & +&- after it .

and you have my thanks .

C++++
Was This Post Helpful? 0
  • +
  • -

#4 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Infix to Postfix

Posted 04 November 2007 - 05:21 PM

The general approach is to convert from infix to pre or post-fix (I have always used postfix for RPN). If you search google for "infix to postfix" you can find many examples (even a snippet on this site). The process is a little involved but not hard (its actually a form of FSM).

Once you have the expression in postfix it is really easy to evaluate.

12-2*9/3 becomes 12 2 9 * 3 / -
How is this evaluated?
well, when you find a number you push it onto the stack, when you find a binary operator you preform the operation on the bottom two elements of the stack the push the result back onto the stack.

so:
push 12
push 2
push 9
pop into operand1, pop into operand2
push operand2 * operand1
push 3
pop into operand1, pop into operand2
push operand2 / operand1
pop into operand1, pop into operand2
push operand2 - operand1

no more elements in input stream? pop answer off stack (whatever is the bottom is considered the answer... in infix to postfix calculations this should be the only thing on the stack, but in RPN calculations this is not always the only element on the stack.)

This is how 99% of the scientific calculators work. They convert infix to postfix and then evaluate.

You CAN evaluate infix directly, but it tends to be a rather complicated.
Was This Post Helpful? 0
  • +
  • -

#5 C++++  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 03-November 07

Re: Infix to Postfix

Posted 05 November 2007 - 12:09 AM

thanks for help that's what i talking about

but how can I write it in C++ ??

( pop & push in this case )
Was This Post Helpful? 0
  • +
  • -

#6 MikeRaines  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 78
  • Joined: 30-October 07

Re: Infix to Postfix

Posted 05 November 2007 - 06:42 AM

O.o Fix positions, this stuff was always very interesting. Good stuff to be learning.

I have some old C code laying around with some fix algorithms I will try to sort through if you are still having issues.
Was This Post Helpful? 0
  • +
  • -

#7 C++++  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 03-November 07

Re: Infix to Postfix

Posted 05 November 2007 - 01:15 PM

Thanks for reply MickRaines ,
I hope you post your codes as fast as you can .

and you have my thanks
C++++
Was This Post Helpful? 0
  • +
  • -

#8 MikeRaines  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 78
  • Joined: 30-October 07

Re: Infix to Postfix

Posted 05 November 2007 - 01:55 PM

Actually there is already a great snippet on this site. Save me some time digging around.

http://www.dreaminco.../snippet490.htm
Was This Post Helpful? 0
  • +
  • -

#9 Topher84  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 113
  • View blog
  • Posts: 359
  • Joined: 04-June 07

Re: Infix to Postfix

Posted 05 November 2007 - 01:56 PM

View PostC++++, on 5 Nov, 2007 - 01:15 PM, said:

Thanks for reply MickRaines ,
I hope you post your codes as fast as you can .

and you have my thanks
C++++


I did something like this a few years ago.. forgot what i made on it but here...

It is in C++

http://www.objectles...tures/index.htm

Lab 2

Feel free to use what you want off the site.. just leave credit :)
Was This Post Helpful? 0
  • +
  • -

#10 C++++  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 03-November 07

Re: Infix to Postfix

Posted 06 November 2007 - 10:22 AM

Thanks for all of you for you informations .I need any thing just tell me

any time and any where .

mohannad_rawha@hotmail.com
or
al_mohannad_007@yahoo.com

thank you a lot guys .

C++++
Was This Post Helpful? 0
  • +
  • -

#11 blacksnake  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 23-July 07

Re: Infix to Postfix

Posted 05 April 2008 - 07:12 PM

i try this code on DEV C++, but i don't see the answer
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1