C program: infix to postfix
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: C program: infix to postfix

  1. #1
    Join Date
    Oct 2005
    Location
    USA
    Posts
    22

    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

    p.s. this is due tomorrow at midnight (11/18 @ 11:59pm)
    Last edited by caramel; November 18th, 2005 at 03:47 PM.
    If you choke a smurf, what color does it turn?

  2. #2
    Join Date
    May 2005
    Location
    Oregon
    Posts
    3,716

    Thumbs up 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
    Last edited by humptydumpty; November 18th, 2005 at 12:51 AM.

  3. #3
    Join Date
    Oct 2005
    Location
    USA
    Posts
    22

    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
    If you choke a smurf, what color does it turn?

  4. #4
    Join Date
    Oct 2005
    Location
    USA
    Posts
    22

    Re: C program: infix to postfix

    how do i convert from c++ to c? i have no prior c++ experience
    If you choke a smurf, what color does it turn?

  5. #5
    Join Date
    Feb 2005
    Location
    Normandy in France
    Posts
    4,590

    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++.
    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=
    "inherit to be reused by code that uses the base class, not to reuse base class code", Sutter and Alexandrescu, C++ Coding Standards.
    Club of lovers of the C++ typecasts cute syntax: Only recorded member.

    Out of memory happens! Handle it properly!
    Say no to g_new()!

  6. #6
    Join Date
    Oct 2005
    Location
    USA
    Posts
    22

    Re: C program: infix to postfix

    Quote Originally Posted by SuperKoko
    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
    If you choke a smurf, what color does it turn?

  7. #7
    Join Date
    Sep 2002
    Location
    14° 39'19.65"N / 121° 1'44.34"E
    Posts
    9,815

    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)...

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center