943,936 Members | Top Members by Rank

Software Development > C++ > Converting equation from infix to postfix using stack
Ad:
  • C++ Discussion Thread
  • Marked Solved
  • Views: 4011
  • C++ RSS
Permalink
Nov 21st, 2007
0

Converting equation from infix to postfix using stack

Expand Post »
I am working on a home work assignment which is:
"Write a program that will allow the user to enter an infix expression terminated by '=' your program will convert to Postfix notation"

enter 3+7-6/2*8+7=
prints 3 7 + 6 2 / 8 * - 7 +

I have written the code below to complete this useing single digits, but I want to allow the user to put in any number and have it do the same
ie 37+47/12 prints 37 47 + 12/

This is not part of the assignment, but I have the next two week to fiddle with it.
Any suggestion? I am lost at the moment.

Thanx in advance!
Lanier

C++ Syntax (Toggle Plain Text)
  1. char InOp1='#'; //Holds values to be compared in switch case.
  2. char InOp2='#'; //Holds value for comparison to properly push onto stack.
  3. LinkedStack Cal; //stack used to hold info in postfix format
  4.  
  5. void In2Post()
  6. 	{
  7. 		cin>>InOp1;
  8.  
  9. 		while(InOp1!='=')
  10. 		{
  11.  
  12. 			//while loop to push digits on to stack
  13. 			while(InOp1!='+'&&InOp1!='-'&&InOp1!='*'&&InOp1!='/'&&InOp1!='('&&InOp1!=')'&&InOp1!='?')
  14. 			{
  15. 				Cal.Push(InOp1);
  16. 				cin>>InOp1;
  17. 			}
  18.  
  19. 			switch(InOp1) //switch case used to properly format stack
  20. 			{
  21. 				case '+': cin>>InOp2;
  22. 					if(InOp2=='+'||InOp2=='-'||InOp2=='*'||InOp2=='/'||InOp2=='('||InOp2==')')
  23. 					{
  24. 						cout<<"Incorrect input "<<InOp2<<" cannot follow + sign."<<endl<<"Must be digit.";
  25. 						InOp1='?';
  26. 						break;
  27. 					}
  28. 					else
  29. 					{
  30. 						Cal.Push(InOp2);
  31. 						Cal.Push(InOp1);
  32. 						cin>>InOp1;
  33. 						break;
  34. 					}
  35. 				case '-': cin>>InOp2;
  36. 					if(InOp2=='+'||InOp2=='-'||InOp2=='*'||InOp2=='/'||InOp2=='('||InOp2==')')
  37. 					{
  38. 						cout<<"Incorrect input "<<InOp2<<" cannot follow - sign."<<endl<<"Must be digit.";
  39. 						InOp1='?';
  40. 						break;
  41. 					}
  42. 					else
  43. 					{
  44. 						Cal.Push(InOp2);
  45. 						Cal.Push(InOp1);
  46. 						cin>>InOp1;
  47. 						break;
  48. 					}
  49. 				case '/': cin>>InOp2;
  50. 					if(InOp2=='+'||InOp2=='-'||InOp2=='*'||InOp2=='/'||InOp2=='('||InOp2==')')
  51. 					{
  52. 						cout<<"Incorrect input "<<InOp2<<" cannot follow / sign."<<endl<<"Must be digit.";
  53. 						InOp1='?';
  54. 						break;
  55. 					}
  56. 					else
  57. 					{
  58. 						Check=Cal.Top();
  59. 						if(Check=='+'||Check=='-')
  60. 						{
  61. 							Cal.Pop();
  62. 							Cal.Push(InOp2);
  63. 							Cal.Push(InOp1);
  64. 							Cal.Push(Check);
  65. 							Check='#';
  66. 							cin>>InOp1;
  67. 							break;
  68. 						}
  69. 						else
  70. 						{
  71. 							Cal.Push(InOp2);
  72. 							Cal.Push(InOp1);
  73. 							Check='#';
  74. 							cin>>InOp1;
  75. 						}
  76. 					}
  77. 				case '*': cin>>InOp2;
  78. 					if(InOp2=='+'||InOp2=='-'||InOp2=='*'||InOp2=='/'||InOp2=='('||InOp2==')')
  79. 					{
  80. 						cout<<"Incorrect input "<<InOp2<<" cannot follow * sign."<<endl<<"Must be digit.";
  81. 						InOp1='?';
  82. 						break;
  83. 					}
  84. 					else
  85. 					{
  86. 						Check=Cal.Top();
  87. 						if(Check=='+'||Check=='-')
  88. 						{
  89. 							Cal.Pop();
  90. 							Cal.Push(InOp2);
  91. 							Cal.Push(InOp1);
  92. 							Cal.Push(Check);
  93. 							Check='#';
  94. 							cin>>InOp1;
  95. 							break;
  96. 						}
  97. 						else
  98. 						{
  99. 							Cal.Push(InOp2);
  100. 							Cal.Push(InOp1);
  101. 							Check='#';
  102. 							cin>>InOp1;
  103. 						}	
  104. 					}
  105. 				case '(':case ')': cin>>InOp1;
  106. 									break;
  107.  
  108. 				default: cout<<endl<<"Input data contains error can not continue."<<endl<<endl;
  109. 						system("pause");
  110. 						return 0;
  111.  
  112. 			}
  113.                 }
Similar Threads
Reputation Points: 10
Solved Threads: 0
Light Poster
LanierWexford is offline Offline
27 posts
since Sep 2007
Permalink
Nov 21st, 2007
0

Re: Converting equation from infix to postfix using stack

The first thing I would suggest is you parse the expression from a string (and not user input), and return an expression list (not void, and not in a global).

You can then test with
C++ Syntax (Toggle Plain Text)
  1. LinkedStack in2post( std::string expr );
  2.  
  3. int main ( ) {
  4.   std::string expr = "3+7-6/2*8+7=";
  5.   LinkedStack result = in2post( expr );
  6. }

You can then expand the tests with
C++ Syntax (Toggle Plain Text)
  1. LinkedStack in2post( std::string expr );
  2.  
  3. int main ( ) {
  4.   std::string expr[] = {
  5.       "1=",
  6.       "1+2=",
  7.       "1+2*3",
  8.       "3+7-6/2*8+7=",
  9.   };
  10.   for ( int i = 0 ; i < sizeof expr / sizeof *expr ; i++ ) {
  11.     LinkedStack result = in2post( expr[i] );
  12.   }
  13. }

When you're finally happy, then you can do
C++ Syntax (Toggle Plain Text)
  1. std::string myExpr;
  2. getline( cin, myExpr );
  3. LinkedStack result = in2post( myExpr );

As far as algorithms go, look up the "shunting yard algorithm".
Team Colleague
Reputation Points: 5862
Solved Threads: 950
Posting Sage
Salem is offline Offline
7,164 posts
since Dec 2005
Permalink
Nov 21st, 2007
0

Re: Converting equation from infix to postfix using stack

I would also suggest better formatting. See this and pay particular attention to the Indentation section. As it is your code is very difficult to follow.
Moderator
Reputation Points: 3278
Solved Threads: 894
Posting Sage
WaltP is online now Online
7,739 posts
since May 2006
Permalink
Nov 21st, 2007
0

Re: Converting equation from infix to postfix using stack

First and formost THANX!! Walt for the link I knew my code was hard to read. Sorry for the bad formatting I will fix that soon.

Also thanx for the idea Sal. I will tweak and report back with the results.

Thanx again

Lanier
Reputation Points: 10
Solved Threads: 0
Light Poster
LanierWexford is offline Offline
27 posts
since Sep 2007
Permalink
Mar 7th, 2008
0

Re: Converting equation from infix to postfix using stack

fck
Reputation Points: 10
Solved Threads: 0
Newbie Poster
chalasesha is offline Offline
8 posts
since Oct 2007

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: Unique way of identifying a document in a subnet
Next Thread in C++ Forum Timeline: Random rotation of a random vector





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC