C program: infix to postfix
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 :cry:
p.s. this is due tomorrow at midnight (11/18 @ 11:59pm)
Re: C program: infix to postfix
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.
Code:
#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
Re: C program: infix to postfix
Quote:
Originally Posted by humptydumpty
thanks but i don't understand most of it, and it's in c++ not c
Re: C program: infix to postfix
how do i convert from c++ to c? i have no prior c++ experience
Re: C program: infix to postfix
Quote:
Originally Posted by caramel
how do i convert from c++ to c? i have no prior c++ experience
This may be an occasion to learn C++. :D
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=
Re: C program: infix to postfix
Quote:
Originally Posted by SuperKoko
lol i was hoping for an easier/quicker way
but thanks :wave:
Re: C program: infix to postfix
Quote:
Originally Posted by caramel
p.s. this is due tomorrow at midnight (11/18 @ 11:59pm)
So it's probably too late by now... Anyway:
Quote:
Originally Posted by caramel
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)... ;)
