How to convert Infix notation to postfix notation

Discussion in 'C Programming' started by Tameem, Oct 26, 2009.

  1. Tameem

    Tameem Guest

    i have a string as (a+b)+8-(c/d) in Infix form.

    how can i convert it to postfix form using C language,,,????
     
    Tameem, Oct 26, 2009
    #1
    1. Advertisements

  2. Tameem

    spinoza1111 Guest

    I will assume that that string is not the ONLY string you have to
    convert. If it is, then the answer is

    int main()
    {
    printf("ab+8+cd/-\n");
    }

    Each one of the following productions should be written as a separate
    C function.

    expression -> additionFactor [ "+"|"-" expression ]
    additionFactor -> multiplicationFactor [ "*"|"/" expression ]
    multiplicationFactor -> term
    term -> LETTER | NUMBER | "(" expression ")" // Rightmost must balance

    Write code using the above "productions" that emits postfix code. For
    each production write one C function. I won't write C for you because
    I don't like C, I suck at it through disuse consequent on my dislike,
    and it's your homework assignment, not mine.

    "->" means "consists of the following material left to right"

    "|" means "or"

    Lower case and camelCase words are grammar categories that will
    correspond to procedures in YOUR code

    Upper case words are lexemes recognised by C code

    Quoted material occurs as is.

    Material in square brackets is optional. An expression could be just
    an additionFactor. In turn an additionFactor can be just a
    multiplicationFactor and a multiplication factor a number. Therefore,
    "3" is an expression.

    When you parse a "term" as "(" expression ")" you must look ahead in
    the overall algorithm I shall give you to find, not the first right
    parenthesis, but the one that actually balances the left parenthesis.
    To do this, maintain a counter. Increment it by one for each left
    parenthesis the lookahead sees: decrement it by one for each right
    parenthesis. When you see right parenthesis and the counter goes to
    zero, you have found the right parenthesis.

    OK, here's the untested and uncompiled C Sharp like pseudo code for
    "expression": convert it to C:

    string expressionMain(string strInstring)
    {
    int intIndex1 = 0;
    string strPolish = "";
    return expression(strInstring, ref intIndex1, ref strPolish);
    }
    string expression(string strInstring, ref int intIndex1, ref string
    strPolish)
    {
    if (!additionFactor(string strInstring,
    ref intIndex1,
    ref strPolish)) return "Not valid";
    if (strInstring[intIndex]=='+' || strInstring[intIndex]=='-')
    {
    int intIndexSave = intIndex1; intIndex1++;
    if (expression(strInstring, ref intIndex1, ref strPolish))
    strPolish += strInstring[intIndexSave];
    else return("Not valid");
    }
    return strPolish;
    }

    C Sharp idioms: ref followed by type in a formal parameter list in a
    function decl is like using asterisk in front of a parameter in C. It
    means that the parameter is passed by reference. In C Sharp, a very
    cool language, you must ALWAYS use the keyword ref in the "actual
    parameters" passed when you call the function just so you know what
    the hell you are doing, as opposed to C which likes to fool you.

    Chapter 3 of my book Build Your Own .Net and Compiler (Edward G.
    Nilges, Apress May 2004) provides a complete solution for this
    homework but in Visual Basic .Net. Therefore this is not a commercial
    promotion. If you find my book useful, buy it, check it out of the
    library, or steal it.
     
    spinoza1111, Oct 26, 2009
    #2
    1. Advertisements

  3. This has very little to do with the /language/ C, i.e., there's
    no "built-in" way to accomplish this conversion. However, it's
    of course possible to implement such a converter in C, e.g., by
    writing a recursive-descent parser (for a good deal of details,
    see <http://en.wikipedia.org/wiki/Operator-precedence_parser>).

    You might also want to take a look at the GNU assembler (gas,
    which is part of the GNU binutils package), which implements
    such a recursive-descent parser to evaluate constant expressions.


    mike
     
    Michael Schumacher, Oct 26, 2009
    #3
  4. Tameem

    Gene Guest

    It this homework?
     
    Gene, Oct 26, 2009
    #4
  5. This is not the usual grammar for expressions and is poor advice for
    someone learning this stuff.
    To the OP: please don't; Spinoza1111 is leading you astray. Post in a
    group about programming (comp.programming is a good one) for better
    advice on how to go about this. Also, if this is homework/coursework,
    be open about that and explain how far you have been able to get on
    your own.

    <snip off-topic C#>
     
    Ben Bacarisse, Oct 26, 2009
    #5
  6. Tameem

    spinoza1111 Guest

    Ben, please indicate the errors and don't imitate Seebach by
    discussing personalities instead of ideas. As it is, you sound like a
    fundamentalist *imam*.
     
    spinoza1111, Oct 27, 2009
    #6
  7. Tameem

    spinoza1111 Guest

    I would have thought given your technical capabilities that you would
    be able, instead of engaging in Fox news style politics of personal
    destruction, to identify all flaws in my approach, whether in the
    formal grammar of C# pseudo code.

    If you cannot, I need an apology from you. NOW, punk.
    C# is what C should be. As I indicated, C Sharp was used as pseudocode
    because it is probably a homework assignment and the OP needs to do
    this homework. The OP probably received poor algorithm guidance from
    the teacher, especially if the teacher was like most people here.
     
    spinoza1111, Oct 27, 2009
    #7
  8. [The formatting errors in the above were added by you. My typing is
    bad, but not /that/ bad.]
    It's not topical here. There must be lots of groups where you can get
    advice on writing a grammar for simple expressions, but I don't know,
    off hand, where would be the best place. I suggested comp.programming
    to the OP, but that is probably not the best place for your question.
    That's OK then.

    <snip>
     
    Ben Bacarisse, Oct 27, 2009
    #8
  9. Tameem

    spinoza1111 Guest

    You have not shown that it is INCORRECT. It's possible that the
    "usual" grammar is incorrect (as in the case of left recursion) given
    Gresham's Law that 99% of everything is crap. You need to show that
    the grammar is either actually incorrect or not suitable for manual
    interpretation, and I do not, personally think you qualified to do so.
    This takes experience in writing an actual parser by hand.

    In the first production it is obvious that on return from
    additionFactor(), the parser can advance the index, and check it for
    greater than end. If the index is past the end, we're done. If it is
    not, the parser can check either for a plus or a minus.

    If either character occurs the parser then calls itself with a source
    string that is necessarily smaller guaranteeing the safety of the
    recursion. But, there must be an expression when there is an operator.

    Disprove this informal logic and desist the Fox news crap, please.
    His goal is to write a C program, but we don't want to give him the
    homework solution. It appears that his instructor in fact knows about
    as much as you about writing a recursive descent parser by hand.
    Therefore he's in the right place.
     
    spinoza1111, Oct 27, 2009
    #9
  10. Tameem

    John Bode Guest

    As others have said, there's no C-specific way of doing this.
    However, here are the general steps you'll need to take:

    First, you will need to separate the string into distinct *tokens*.
    In your example, you have four kinds of tokens -- operators
    ('+','-','*','/'), separators ('(',')'), constants ('8'), and
    identifiers ('a','b','c','d'). Generally, you'll have a set of rules
    that determines what characters make up a particular kind of token
    (for example, an identifier must start with a letter and consist of
    only letters and digits: "a1", "foo", "x", etc.). As you scan each
    character, you'll check against the currently active rule and if it
    matches, you'll add it to the token.

    There are two ways to go on the next step. You can either build a
    full-blown recursive descent parser (a decent explanation appears on
    Wikipedia), or you can use a simple stack-based converter. For the
    stack-based converter, as you read the expression, you'll pass
    constants and identifiers straight to output, and you'll push and pop
    operators on the stack based on their precedence. If the operator on
    the top of the stack has a lower precedence than the current operator,
    then push the current operator. If the operator on the stack has an
    equal or higher precedence than the current operator, then pop the
    operator off the stack and write it to output, then push the current
    operator on the stack. lparens are always pushed onto the stack;
    rparens cause everything on the stack to be popped to the next
    lparen. Neither lparens nor rparens are written to output.

    Given your example, the operations would look something like this:

    1. Read '(', push it onto the stack. Stack contents = {'('}
    2. Read 'a', write it to output. Output string = "a"
    3. Read '+', push it on the stack: {'(', '+'}
    4. Read 'b', write it to output: "a b"
    5. Read ')', pop everything off the stack to the next '(', but don't
    write '(' to output. Output string is "a b +", stack contents = {}
    6. Read '+', push it onto the stack: {'+'}
    7. Read '8', write it to output: "a b + 8"
    8. Read '-', has same precedence as '+', so pop '+' from stack, write
    it to output, and push '-': "a b + 8 +", {'-'}
    9. Read '(', push it onto the stack: {'-', '('}
    10. Read 'c', write it to output: "a b + 8 + c"
    11. Read '/', push onto stack: {'-', '(', '/'}
    12. Read 'd', write to output: "a b + 8 + c d"
    13. Read ')', pop everything to '(': "a b + 8 + c d /", {'-'}
    14. End of string, pop remainder of stack: "a b + 8 + c d / -"
     
    John Bode, Oct 27, 2009
    #10
  11. Quibble. Sturgeon's law (although the story may be apocryphal and/or
    tongue-in-cheek).

    Gresham's law says that the bad drives out the good, which is, not
    coincidentally, also very true and on display in comp.lang.c
     
    Kenny McCormack, Oct 27, 2009
    #11
  12. Tameem

    spinoza1111 Guest

    Might be overkill given that the problem statement implies that
    symbols are a letter, and scanning non-integer tokens might be beyond
    the requirements of the problem...since the OP's teacher hasn't told
    him what a number is, and a fully general number recognizer that
    recognizes signs, exponents, and decimal points is a project in
    itself. Therefore a number is probably an integer, and this can be
    recognized by adhoc code. A separate pass for lexical analysis is
    probably overkill.
    Very nice and correct, perhaps clearer than a grammar based solution,
    with the caveats that when the top of the stack is an LP, anything
    other than RP must be stacked and RP is an error. Also may not catch
    some errors.
     
    spinoza1111, Oct 28, 2009
    #12
  13. Tameem

    spinoza1111 Guest

    Give me a break. What part of hyperbole don't you faggots understand?
    Furthermore, any claims you might have had to being treated in a
    politically correct fashion were made moot when you started to join
    electronic mobs and to propagate lies about individuals here. Frankly,
    I do not understand groups who form identities as "oppressed" and
    their claims to be spoken about in a civil fashion when they do not
    extend this civility towards others or their own members.

    According to some of my sources, systematic "trashing" of targeted
    individuals began in the women's movement as the complement to women's
    demands to be spoken of in a new language cleansed of "honey" and
    "babe". It was directed at women inside the movement. Likewise, Larry
    Kramer, a gay man, has spoken of the way in which gay people demand
    kid glove treatment and cleansed language from straights...while
    trashing each other and infecting each other with AIDs.

    Groups demand charity that is denied, that they deny, to individuals.
     
    spinoza1111, Oct 28, 2009
    #13
  14. Tameem

    spinoza1111 Guest

    Ben Bacarisse noticed that I used the wrong grammar and informed me by
    email in a very professional way. The grammar should be the following
    for direct conversion to code!!

    expression → additionFactor [ "+"|"-" additionFactor ] *
    additionFactor → multiplicationFactor [ "*"|"/" multiplicationFactor ]
    *
    multiplicationFactor → LETTER | NUMBER | "(" expression ")"

    That is, an expression is a series of one or more additionFactors.
    When there are at least two, they are separated by plus or minus. The
    replacement of the right recursive call to expression by the iteration
    over additionFactor (the asterisk expressing iteration) causes the
    addition/subtraction to left associate naturally. Likewise for the
    call to expression in the second production.

    I also made this same error when developing the code for Build Your
    Own .Net Language and Compiler but did not have Ben Bacarisse's expert
    assistance. Instead, I discovered it in testing the code for the first
    toy compiler in ch 3 and mention the problem, and its solution, in my
    book. I was too lazy when posting to check my own goddamn book and
    shall try to be more diligent in the future. However, such diligence
    shall be pearls before swine in some cases and in others the exception
    that proves the rule.

    When I make an error I make each error twice, it seems to give the old
    brain extra time to relearn things it learned in the past; in the past
    week I have made the comma-as-operator-versus-separator as well as
    this error twice. I do regret if the original post was useless to the
    original poster, because as Ben pointed out, it right-associative.

    But (big but): my post was of far greater quality, errors and all,
    that the uncollegial crap which constitutes 99% of the postings here.
    As was Ben's correction. This dialogue is what this facility should be
    all the time, not denials that something is true unaccompanied by
    information as to what is, and the politics of personal destruction.

    Because of this, no response to this thread by Richard Heathfield will
    be either read by me nor responded to by me.

    Ben: thanks for your assistance and the very professional manner in
    which you made it. If there are other errors please let me know.
    Likewise for all other readers, except Richard Heathfield. I do not
    think he's qualified to discuss this issue.
     
    spinoza1111, Oct 28, 2009
    #14
  15. Tameem

    spinoza1111 Guest

    Here is a C Sharp implementation of recursive descent to translate
    infix to Polish notation. It runs as a command line program. If an
    infix expression is entered in its command line, this expression is
    converted to Polish notation and the result is displayed.

    If the command line contains no operands, a test suite is run. It
    should produce this output:

    Expect "2 4 3 + /": "2 4 3 + /"
    Expect "2 4 / 3 +": "2 4 / 3 +"
    Expect "2 4 3 + /": "2 4 3 + /"
    Expect "10 113 2 2 4 3 + / + 2 + 2 + - + a *": "10 113 2 2 4 3 + / + 2
    + 2 + - + a *"
    Expect error: "Error detected at or near character 3 in "11+":
    Addition or subtraction operator is not followed by addFactor"
    Expect error: "Error detected at or near character 2 in "11 +":
    Expected addition or subtraction operator not found"
    Expect "10 113 + a *": "10 113 + a *"
    Expect "10 113 + a *": "10 113 + a *"
    Expect "1": "1"
    Expect "a b + c -": "a b + c -"
    Expect "1 1 +": "1 1 +"

    Here is the code. It should constitute the complete Program.CS file in
    a .Net C Sharp command line mode application. It was tested under .Net
    C Sharp Express, a free product available from Microsoft. Comments are
    welcome.

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace infix2Polish
    {
    class Program
    {
    static void Main(string[] strArgs)
    {
    if (strArgs.GetUpperBound(0) < 0)
    Console.WriteLine(tester());
    else
    Console.WriteLine(infix2Polish(strArgs[0]));
    return;
    }

    private static string tester()
    {
    return "Expect \"2 4 3 + /\": \"" +
    infix2Polish("2/(4+3)") + "\"" +
    Environment.NewLine +
    "Expect \"2 4 / 3 +\": \"" +
    infix2Polish("2/4+3") + "\"" +
    Environment.NewLine +
    "Expect \"2 4 3 + /\": \"" +
    infix2Polish("((2/(4+3)))") + "\"" +
    Environment.NewLine +
    "Expect " +
    "\"10 113 2 2 4 3 + / + 2 + 2 " +
    "+ - + a *\": \"" +
    infix2Polish
    ("((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a") +
    "\"" +
    Environment.NewLine +
    "Expect error: \"" +
    infix2Polish("11+") + "\"" +
    Environment.NewLine +
    "Expect error: \"" +
    infix2Polish("11 +") + "\"" +
    Environment.NewLine +
    "Expect \"10 113 + a *\": \"" +
    infix2Polish("(10+113)*a") + "\"" +
    Environment.NewLine +
    "Expect \"10 113 + a *\": \"" +
    infix2Polish("((10+113))*a") + "\"" +
    Environment.NewLine +
    "Expect \"1\": \"" +
    infix2Polish("1") + "\"" +
    Environment.NewLine +
    "Expect \"a b + c -\": \"" +
    infix2Polish("a+b-c") + "\"" +
    Environment.NewLine +
    "Expect \"1 1 +\": \"" +
    infix2Polish("1+1") + "\"" +
    Environment.NewLine;
    }

    private static string infix2Polish(string strInfix)
    {
    string strPolish = "";
    int intIndex1 = 0;
    string strErrorMessage = "";
    if (!expression(strInfix,
    ref strPolish,
    ref intIndex1,
    ref strErrorMessage))
    return strErrorMessage;
    return strPolish.Trim();
    }

    private static bool expression
    (string strInfix,
    ref string strPolish,
    ref int intIndex,
    ref string strErrorMessage)
    {
    return expression(strInfix,
    ref strPolish,
    ref intIndex,
    ref strErrorMessage,
    strInfix.Length - 1);
    }
    private static bool expression
    (string strInfix,
    ref string strPolish,
    ref int intIndex,
    ref string strErrorMessage,
    int intEnd)
    {// expression -> addFactor [ +|- addFactor ] *
    if (!addFactor(strInfix,
    ref strPolish,
    ref intIndex,
    ref strErrorMessage,
    intEnd))
    return errorHandler
    (strInfix,
    intIndex,
    ref strErrorMessage,
    "Expression doesn't start with " +
    "addFactor");
    char chrAddOp = ' ';
    while (intIndex <= intEnd)
    {
    if ((chrAddOp = strInfix[intIndex]) != '+'
    &&
    chrAddOp != '-')
    return errorHandler
    (strInfix,
    intIndex,
    ref strErrorMessage,
    "Expected addition or subtraction " +
    "operator not found");
    intIndex++;
    if (intIndex > intEnd
    ||
    !addFactor(strInfix,
    ref strPolish,
    ref intIndex,
    ref strErrorMessage,
    intEnd))
    return errorHandler
    (strInfix,
    intIndex,
    ref strErrorMessage,
    "Addition or subtraction " +
    "operator is not followed by " +
    "addFactor");
    strPolish += chrAddOp.ToString() + ' ';
    }
    return true;
    }

    private static bool addFactor
    (string strInfix,
    ref string strPolish,
    ref int intIndex,
    ref string strErrorMessage,
    int intEnd)
    {// addFactor -> mulFactor [ *|/ mulFactor ] *
    if (!mulFactor(strInfix,
    ref strPolish,
    ref intIndex,
    ref strErrorMessage,
    intEnd))
    return errorHandler
    (strInfix,
    intIndex,
    ref strErrorMessage,
    "Expected multiplication factor " +
    "not found");
    char chrMulOp = ' ';
    while (intIndex <= intEnd
    &&
    ((chrMulOp = strInfix[intIndex]) == '*'
    ||
    chrMulOp == '/'))
    {
    intIndex++;
    if (intIndex > intEnd
    ||
    !mulFactor(strInfix,
    ref strPolish,
    ref intIndex,
    ref strErrorMessage,
    intEnd))
    return errorHandler
    (strInfix,
    intIndex,
    ref strErrorMessage,
    "Expected multiplication factor " +
    "not found");
    strPolish += chrMulOp.ToString() + ' ';
    }
    return true;
    }

    private static bool mulFactor
    (string strInfix,
    ref string strPolish,
    ref int intIndex,
    ref string strErrorMessage,
    int intEnd)
    {// mulFactor -> LETTER|NUMBER|"(" expression ")"
    if (strInfix[intIndex] >= 'a'
    &&
    strInfix[intIndex] <= 'z')
    {
    strPolish += strInfix[intIndex++].ToString() +
    ' ';
    return true;
    }
    int intIndex1 = intIndex;
    while(intIndex <= intEnd
    &&
    (strInfix[intIndex] >= '0'
    &&
    strInfix[intIndex] <= '9'))
    strPolish += strInfix[intIndex++];
    if (intIndex > intIndex1)
    {
    strPolish += ' ';
    return true;
    }
    if (strInfix[intIndex] == '(')
    {
    intIndex++;
    int intLevel = 1;
    int intIndexAhead = 0;
    for (intIndexAhead = intIndex;
    intIndexAhead <= intEnd;
    intIndexAhead++)
    {
    switch (strInfix[intIndexAhead])
    {
    case '(':
    {
    intLevel++; break;
    }
    case ')':
    {
    intLevel--;
    if (intLevel == 0) goto exit;
    break;
    }
    default: break;
    }
    }
    exit:
    if (!expression(strInfix,
    ref strPolish,
    ref intIndex,
    ref strErrorMessage,
    intIndexAhead - 1))
    return errorHandler
    (strInfix,
    intIndex,
    ref strErrorMessage,
    "Nested expression invalid");
    intIndex++;
    }
    return true;
    }

    private static bool errorHandler
    (string strInfix,
    int intIndex,
    ref string strBase,
    string strMessage)
    {
    strBase +=
    (strBase == "" ? "" : "; ") +
    "Error detected at or near " +
    "character " +
    intIndex.ToString() + " " +
    "in " + "\"" + strInfix + "\": " +
    strMessage;
    return false;
    }
    }
    }
     
    spinoza1111, Oct 31, 2009
    #15
  16. Tameem

    spinoza1111 Guest

    I published it here to show the OP that the grammar based approach
    works, and give him "pseudo code" for his C assignment, without doing
    his homework for him.

    Since by now he's probably handed in his assignment, I challenge you
    to translate the C Sharp code to C. Should be easy since you're such a
    Studly Dudley C programmer. >
     
    spinoza1111, Oct 31, 2009
    #16
  17. That would not be useful. Your code does not parse the language
    defined by the grammar, and what it does do, it does in a rather
    roundabout way.

    <snip>
     
    Ben Bacarisse, Nov 1, 2009
    #17
  18. Tameem

    spinoza1111 Guest

    If you think the grammar is correct, say so clearly. You imply it but
    are too graceless to say it. Now the issue is whether the code
    supports the correct grammar correctly.

    You present no evidence for the first claim. As to the second, it
    means you've never seen this simple algorithm.
     
    spinoza1111, Nov 1, 2009
    #18
  19. Tameem

    spinoza1111 Guest

    Did you write it or did you steal it?
    I need to see you actually write new C code. You have a big mouth when
    it comes to putting down people but the only time when you put your
    big mouth on the line (the Spark Notes test) you failed. I am giving
    you another chance.

    I wrote and debugged a recursive descent parser for my book. I wrote
    it again here after correcting the grammar because I think it's
    incumbent on each one of us to be able to orally present an algorithm,
    and writing it anew and posting it for comments simulates this oral
    presentation.

    It also demonstrates that the material is sufficiently complex for
    smart people to make stupid mistakes (Knuth has himself said he
    consistently gets binary search wrong the first time), and that the
    stupid people aren't the ones making the mistakes.

    It's the people too ready to trash and if possible render unemployable
    their fellow human beings (by creating a record here) while explaining
    away their own mistakes as you explained away your failure to get a
    decent grade on the Spark Notes test.

    You are as such contemptible.
     
    spinoza1111, Nov 1, 2009
    #19
  20. Tameem

    Seebs Guest

    Presumably wrote it. I mean, come on. A parser is NOT that hard; I've
    written one from scratch (maybe two) and done a few with yacc, and while
    the code in question doubtless sucked (hint: everyone's first language
    sucks), it worked fine.
    Er, why?
    .... Wait, SPARK NOTES?

    You're telling me that you are comparing Richard Heathfield to SPARK NOTES
    and you think that a discrepancy means he's wrong?

    Please tell me that it's still Halloween where you are and you went as
    a troll.
    .... Wait, uhm.

    Does that mean the one in the book is wrong?

    If so, then how did this not show up in debugging?
    Stupid people make mistakes too.
    I am totally fascinated by the concept of such a test. Is it ...
    Hmm.

    Well, I went and looked, and found:

    http://www.sparknotes.com/cs/pointers/review/quiz.html

    This is a funny quiz. It is full of errors.

    Is this the quiz you used?

    Please let me know.

    -s
     
    Seebs, Nov 1, 2009
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.