Re: How to convert Infix notation to postfix notation

On Oct 26, 2:30 pm, spinoza1111 <spinoza1...@xxxxxxxxx> wrote:
On Oct 26, 12:33 pm, Tameem <etam...@xxxxxxxxx> wrote:

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

how can i convert it to postfix form using C language,,,????

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.

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

Relevant Pages

  • Re: How to convert Infix notation to postfix notation
    ... I will assume that that string is not the ONLY string you have to ... parenthesis, but the one that actually balances the left parenthesis. ... return expression(strInstring, ref intIndex1, ref strPolish); ...
    (comp.lang.c)
  • Re: Reg Ex Challenge
    ... 'Finds an opening string, then searches for a closing string. ... Dim aRange As Word.Range ... ask if you want to extend to another closing parenthesis. ...
    (microsoft.public.word.vba.general)
  • VSTO 2005 COM Add-In Word Buttons not responding after first click
    ... connectMode, object addInInst, ref System.Array custom) ... DME.SearchResults objSearchResults; ... string sDocumentID = null; ... sDocumentID = oForm.txtDocID.Text; ...
    (microsoft.public.office.developer.com.add_ins)
  • Re: How to convert Infix notation to postfix notation
    ... Briefly it failed for a null string and a blank. ... letter without checking intIndex for being out of bounds. ... ref strPolish, ... ref strErrorMessage, ...
    (comp.lang.c)
  • Re: local path
    ... public static extern int WNetGetUniversalName( ... ref StringBuilder lpBuffer, ... public string ConvertLocalPathToUnc( ... ref buffer, ref size); ...
    (microsoft.public.dotnet.framework)