C program: infix to postfix

[caramel]

i am to write a program that converts an expression (entered by user) from infix notation to postfix notation. the expressions will only consist of single-character variables: a, b, c, …, A, B, C, … ; single-digit decimal numbers: 0, 1, 2, …, 9 ; left and right parentheses: (, ) ; and only the following set of operators: *, /, +, -

and specifications of the assignment are as follows:
• When testing, consider using the “if” and “if else”, or “while” control structures. You must use the
“switch” conditional control structure when testing for Operator symbols.
• Variable (letter) or number – print it.
• Left parenthesis – push onto stack.
• Right parenthesis – pop and print each operator from the stack until a left parenthesis is found.
Discard (do not print) both parentheses. If the null character gets to the top of the stack before a left
parenthesis, then the parentheses were unbalanced – this is an unrecoverable error.
• Operator symbol:
− If this symbol has a higher precedence than the operator at the top of stack, push this symbol
onto the stack.
− If this symbol has a lower or equal precedence than the operator at the top of stack, pop and print
the symbol from the top of stack. (Note that the null character on the stack should be treated as
an operator with the lowest precedence.)
− Keep doing this rule until the current symbol gets pushed onto the stack.
− You must use the “switch” conditional control structure when testing for Operator
symbols.
• Null character – pop and print all operators from the stack. If a left parenthesis appears on the stack
during this process, then the parentheses were unbalanced – this is an unrecoverable error.

* Note that only operators and left parentheses will ever be pushed onto the stack.


You must
write a main() function that does the following:
1. Allocate a character array that will hold a string of at least 40 characters.

2. Read an input string from the user and put it in the allocated array. Assume that the string will be a
legal infix-notation expression, using only the characters specified above. In other words, you don't
need to test for multi-character symbols or other characters. There must be no whitespace
characters in the expression, or else a single scanf will not work.

3. Process each character of the array (string), using the rules above, printing the postfix expression to
the console (using printf).

4. If an error is found during expression processing, caused by unbalanced parentheses, then print
"ERROR: Unbalanced parentheses" and exit the program. (You can use the return statement inside
the main function to exit the program.) Here are some examples that you can use to test your
program. In each pair, the top line is the input string, and the bottom line is what should be printed by
your program.

Infix: a*b+c*d/2 Postfix: ab*cd*2/+
Infix: a&b+c*d Postfix: abcd*+&
Infix: (a&b)+c*d Postfix: ab&cd*+
Infix: A*((B+C)*D)/2 Postfix: ABC+D**2/
Input: (a+b Output: ab+ERROR: Unbalanced parentheses
Input: a+b) Output: ab+ERROR: Unbalanced parentheses
Input: a*b+((c*d)/2 Output: ab*cd*2/ERROR:Unbalanced parentheses


problems:

• it works well with variables but ignores numbers.

• i don't know how to implement a switch in place of what i already have

• and the error thing too, i'm not sure how to detect that

help

p.s. this is due tomorrow at midnight (11/18 @ 11:59pm)

[humptydumpty]

Just go with the link

http://www.faqts.com/knowledge_base/.../28152/fid/163

fine here here is one in C++ you can change it in C i think very easily not too hard.

 
#include <iostream>
#include <string>
#include <stack>
using namespace std;
 
void Convert(const string & Infix, string & Postfix);
bool IsOperand(char ch);
bool TakesPrecedence(char OperatorA, char OperatorB);
 
int main(void)
{
char Reply;
do
	 {
	 string Infix, Postfix; // local to this loop
	 cout << "Enter an infix expression (e.g. (a+b)/c^2, with no 
spaces):"
		 << endl;
	 cin >> Infix;
	 Convert(Infix, Postfix);
	 cout << "The equivalent postfix expression is:" << endl
		 << Postfix << endl;
	 cout << endl << "Do another (y/n)? ";
	 cin >> Reply;
	 }
while (tolower(Reply) == 'y');
return 0;
}
 
/* 
Given: ch A character.
Task: To determine whether ch represents an operand (here 
understood to be a single letter or digit).
Return: In the function name: true, if ch is an operand, false 
otherwise.
 
*/
 
bool IsOperand(char ch)
{
if (((ch >= 'a') && (ch <= 'z')) ||
	 ((ch >= 'A') && (ch <= 'Z')) ||
	 ((ch >= '0') && (ch <= '9')))
	 return true;
else
	 return false;
}
 
/* Given:
 OperatorA	A character representing an operator or 
parenthesis.
OperatorB	A character representing an operator or 
parenthesis.
Task: To determine whether OperatorA takes precedence over OperatorB.
 
Return: In the function name: true, if OperatorA takes precedence 
over	 OperatorB.
*/
bool TakesPrecedence(char OperatorA, char OperatorB)
{
if (OperatorA == '(')
	 return false;
else if (OperatorB == '(')
	 return false;
else if (OperatorB == ')')
	 return true;
else if ((OperatorA == '^') && (OperatorB == '^'))
	 return false;
else if (OperatorA == '^')
	 return true;
else if (OperatorB == '^')
	 return false;
else if ((OperatorA == '*') || (OperatorA == '/'))
	 return true;
else if ((OperatorB == '*') || (OperatorB == '/'))
	 return false;
else
	 return true;
 
}
 
/* Given: Infix	A string representing an infix expression (no spaces).
Task: To find the postfix equivalent of this expression.
Return: Postfix A string holding this postfix equivalent.
*/
 
void Convert(const string & Infix, string & Postfix)
{
stack<char> OperatorStack;
char TopSymbol, Symbol;
int k;
for (k = 0; k < Infix.size(); k++)
	 {
	 Symbol = Infix[k];
	 if (IsOperand(Symbol))
		 Postfix = Postfix + Symbol;
	 else
		 {
		 while ((! OperatorStack.empty()) &&
			(TakesPrecedence(OperatorStack.top(), Symbol)))
			{
			TopSymbol = OperatorStack.top();
			OperatorStack.pop();
			Postfix = Postfix + TopSymbol;
			}
		 if ((! OperatorStack.empty()) && (Symbol == ')'))
			OperatorStack.pop(); // discard matching (
		 else
			OperatorStack.push(Symbol);
		 }
	 }
while (! OperatorStack.empty())
	 {
	 TopSymbol = OperatorStack.top();
	 OperatorStack.pop();
	 Postfix = Postfix + TopSymbol;
	 }
}

and here is another in c
Have a look on this for all algo in a very efficient manner
http://www.cs.man.ac.uk/~pjj/cs2121/fix.html

[caramel]

Just go with the link

http://www.faqts.com/knowledge_base/.../28152/fid/163

thanks but i don't understand most of it, and it's in c++ not c

[caramel]

how do i convert from c++ to c? i have no prior c++ experience

[SuperKoko]

how do i convert from c++ to c? i have no prior c++ experience

This may be an occasion to learn C++.
This link may help you to understand C++ without knowing C++: http://www.4p8.com/eric.brasseur/cppcen.html#l15

And for further learning:
http://www.google.com/search?hl=fr&q...Rechercher&lr=

[caramel]

This may be an occasion to learn C++.
This link may help you to understand C++ without knowing C++: http://www.4p8.com/eric.brasseur/cppcen.html#l15

And for further learning:
http://www.google.com/search?hl=fr&q...Rechercher&lr=

lol i was hoping for an easier/quicker way

but thanks

[gstercken]

p.s. this is due tomorrow at midnight (11/18 @ 11:59pm)

So it's probably too late by now... Anyway:

i don't know how to implement a switch in place of what i already have

Well, what do you already have? It would be easier to help if you posted the code (using code tags, please, and no bold type)...