How to convert Infix notation to postfix notation

[Tameem]

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

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

 

[spinoza1111]

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.

 

[Michael Schumacher]

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

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

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

 

[Gene]

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

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

It this homework?

 

[Ben Bacarisse]

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

This is not the usual grammar for expressions and is poor advice for
someone learning this stuff.

Write code using the above "productions" that emits postfix code.

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

 

[spinoza1111]

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

This is not the usual grammar for expressions and is poor advice for
someone learning this stuff.

Write code using the above "productions" that emits postfix code.

To the OP: please don't;Spinoza1111is leading you astray.  Post in a

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]

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

This is not the usual grammar for expressions and is poor advice for
someone learning this stuff.

Write code using the above "productions" that emits postfix code.

To the OP: please don't;Spinoza1111is leading you astray.  Post in a

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.

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

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.

 

[Ben Bacarisse]

spinoza1111<[email protected]> writes:

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

This is not the usual grammar for expressions and is poor advice for
someone learning this stuff.

Write code using the above "productions" that emits postfix code.

To the OP: please don't;Spinoza1111is leading you astray.  Post in a

[The formatting errors in the above were added by you. My typing is
bad, but not /that/ bad.]

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.

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.

If you cannot, I need an apology from you. NOW, punk.

That's OK then.

<snip>

 

[spinoza1111]

spinoza1111<[email protected]> writes:

expression -> additionFactor [ "+"|"-" expression ]
additionFactor -> multiplicationFactor [ "*"|"/" expression ]
multiplicationFactor -> term
term -> LETTER | NUMBER | "(" expression ")" // Rightmost must balance
This is not the usual grammar for expressions and is poor advice for
someone learning this stuff.

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.

[The formatting errors in the above were added by you.  My typing is
bad, but not /that/ bad.]

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.

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.

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.

 

[John Bode]

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

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

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 / -"

 

[Kenny McCormack]

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

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

 

[spinoza1111]

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.

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.

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.

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]

<snip>
expression -> additionFactor [ "+"|"-" expression ]
additionFactor -> multiplicationFactor [ "*"|"/" expression ]
multiplicationFactor -> term
term -> LETTER | NUMBER | "(" expression ")" // Rightmost must balance
This is not the usual grammar for expressions and is poor advice for
someone learning this stuff.

You have not shown that it is INCORRECT.

No, and I never said it was.  You know where to post if you really
don't know what is wrong with it.  I don't want to be drawn further
into an off topic discussion of grammars here.  Only in a suitable
group will you get the very best advice; and only there would any
criticism be properly checked.  Send me an email (drop the ".usenet"
to get through faster) if you really can't bear to post in a suitable
group, but then neither of us will benefit from third party scrutiny.

Alternatively, feel free to have the last word by calling me
"unqualified" or a "******" again.  I grew up gay being called a lot
worse than "unqualified".

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]

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.

 

[spinoza1111]

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.- Hide quoted text -

- Show quoted text -

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]

In

spinoza1111wrote:



The microsoft.public.dotnet.languages.csharp newsgroup exists for C#
discussions; posting your code there will give you the best chance of
getting informed reviews of that code.

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

 

[Ben Bacarisse]

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.

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>

 

[spinoza1111]

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.

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]

In

spinoza1111wrote:


If the OP is wise, he will treat any of your code, in whatever
language, with a great deal of suspicion.



I see no value in reinventing that particular wheel. I already have
working recursive descent code. What would be the point in

Did you write it or did you steal it?

translating yours? If it works (which I doubt), I gain nothing. If 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.

 

[Seebs]

Did you write it or did you steal it?

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.

I need to see you actually write new C code.

Er, why?

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.

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

I wrote and debugged a recursive descent parser for my book. I wrote
it again here after correcting the grammar

.... Wait, uhm.

Does that mean the one in the book is wrong?

If so, then how did this not show up in debugging?

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.

Stupid people make mistakes too.

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.

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