How to convert Infix notation to postfix notation

S

spinoza1111

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?

Because I don't think you're competent.
... 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?

Yes. The anonymous team who drafted the Spark Notes test were more
competent than Heathfield, just as Schildt is also more competent than
you.

Note that I don't say "at C" because to be competent at a mistake is
to be subhuman. No, I mean more competent human beings. You know what
a human being is, don't you?
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?

No. Like many smart people without serious personality disorders I
make typical mistakes: Knuth has confessed he makes the same mistake
in binary search each time he implements it anew. These brain farts
show that we're thinking non-autistically, like actual human beings.
You know what a human being is, or used to be?

I made the same error while developing the book but while coding
noticed it was wrong, and corrected it, using my mistake to explain
things.

I don't have to be right all the time whereas you must be since
otherwise you're a frightened little boy.
If so, then how did this not show up in debugging?

It didn't show since fixed it. As I've said, I made the mistake
twice: in 2003 while writing the book, and last week when replying to
the OP.
Stupid people make mistakes too.

Arguably less than smart people because stupid people have to work at
7-11 where their actions are monitored, or on funny little embedded
systems as opposed to actually important systems such as Microsoft
boxes, and their work is constantly checked.
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.

Document each error. Is that why you failed to graduate properly and
did not get an MSCS? You sat in the test finding errors instead of
answering questions?
Is this the quiz you used?

Please let me know.

You're not really worth it.
 
S

Seebs

Because I don't think you're competent.

Wait, me too, or just Richard?
Yes. The anonymous team who drafted the Spark Notes test were more
competent than Heathfield, just as Schildt is also more competent than
you.

.... What the ****?
Note that I don't say "at C" because to be competent at a mistake is
to be subhuman.

You clearly do not understand why Buster Keaton rocks.
No, I mean more competent human beings. You know what
a human being is, don't you?

Normally, yes.

However, even if we grant that they're hypothetically competent
at "being human beings" or whatever, that still doesn't make their test
informative as to whether someone knows C.

And come to think of it... It sounds like you've just asserted that,
if Richard Heathfield can write C competently, that makes him subhuman.
You're not exactly making a persuasive argument here that he should show
you how good his code is.
No. Like many smart people without serious personality disorders I
make typical mistakes:

This is also true of stupid people without serious personality disorders,
smart people with serious personality disorders, or stupid people with
serious personality disorders.
Knuth has confessed he makes the same mistake
in binary search each time he implements it anew. These brain farts
show that we're thinking non-autistically, like actual human beings.

Actually, they don't. Because autistic people make those same kinds of
mistakes.
I don't have to be right all the time whereas you must be since
otherwise you're a frightened little boy.

This would be much, much, more persuasive if I hadn't admitted to at least
half a dozen errors in comp.lang.c in the last month or so.
Arguably less than smart people because stupid people have to work at
7-11 where their actions are monitored, or on funny little embedded
systems as opposed to actually important systems such as Microsoft
boxes, and their work is constantly checked.

Oh, I see. You're trying to sneakily imply that I'm stupid. No, not buying
it. I certainly have my cognitive flaws, but "stupidity" is not one
of them.
Document each error.

I'll just give you my favorite:

After this code executes

int arr[10];
int i;
i = &arr[9] - arr;

what is the value of i?
(A) 8
(B) 9
(C) 10
(D) Won't compile

Go ahead, guess what their answer is. Guess what mine was. And guess
what my compiler says if I try it. :) (Hint: The last two are both
the correct answer. Theirs isn't.)
Is that why you failed to graduate properly and
did not get an MSCS?

Who said I failed to graduate properly? I graduated just fine with a BA.
I didn't feel like doing more school at the time, so I just started going out
and doing stuff.
You sat in the test finding errors instead of
answering questions?

Funny thing, when I was doing tests written by college professors rather
than by random people on the internet, I didn't find nearly so many errors.
:)
You're not really worth it.

From which I infer that this WAS the test you used, or part of the same test,
and that the idea that there might be unambiguous errors in that test would
undermine the quality of your argument against Richard Heathfield?

-s
 
S

Seebs

For the benefit of those who may not know, the subject of the Spark
Notes test in question was C++, not C.

Oh, then it was a different one.

Looking at this one, though, I think I would share your evaluation. Many
of the questions are ambiguous or poorly phrased, a few are just plain
wrong.

-s
 
S

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.

<snip>

Since Ben is too lazy and too discourteous to reply with errors, I
shall reply with errors in the code that I found when starting to
convert it to C.

Briefly it failed for a null string and a blank.

It failed (out of bounds subscript) in the mulFactor recognizer when
the infix expression was a null string. This is because mulFactor is
what would be in a more elaborate parser a lexxer looking to the next
character and returning some agreed on symbol when the input is at an
end. Therefore, mulFactor has to take responsibility in the absence of
a lexxer for detailed pointer checks. It started by looking for a
letter without checking intIndex for being out of bounds.

It needed this check. The second test in mulFactor did not since the
bounds check is part of the while condition. But the third test for a
left parenthesis also needed this check.

I put a new check at the start of mulFactor, returning false when
intIndex>intEnd. I also added a false and error return when mulFactor,
which again combines the jobs of mulFactor and lex, fails to find one
of its three alternatives: letter, number, parenthesized expression. I
also made the output of the regression test more readable.

Note that people who make mistakes learn more even if like Knuth wrt
binary search they make them more than once, IF they are not
constantly interrupted by autistic twerps. They also teach more.

There may have been other mistakes in this code. I have neither
formally nor informally proved it correct. But apart from making an
unsupported claim, Bacarisse has as yet provided no insights. I have
had to do so, so far, wrt to the null string and blank character bug.

Nothing could more clearly indicate the pathology of a newsgroup so
dominated by autistic twerps.

Here is the new test regression output, followed by the new code.


Expect "": For the infix expression "", the Polish expression or error
report is

Error detected at or near character 0 in "": Expected multiplication
factor not found; Error detected at or near character 0 in "":
Expression doesn't start with addFactor
--------------------------------------------
Expect "": For the infix expression " ", the Polish expression or
error report is

Error detected at or near character 0 in " ": Unexpected character '
'; Error detected at or near character 0 in " ": Expected
multiplication factor not found; Error detected at or near character 0
in " ": Expression doesn't start with addFactor
--------------------------------------------
Expect "2 4 3 + /": For the infix expression "2/(4+3)", the Polish
expression or error report is

2 4 3 + /
--------------------------------------------
Expect "2 4 / 3 +": For the infix expression "2/4+3", the Polish
expression or error report is

2 4 / 3 +
--------------------------------------------
Expect "2 4 3 + /": For the infix expression "((2/(4+3)))", the Polish
expression or error report is

2 4 3 + /
--------------------------------------------
Expect "10 113 2 2 4 3 + / + 2 + 2 + - + a *": For the infix
expression "((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a", the Polish
expression or error report is

10 113 2 2 4 3 + / + 2 + 2 + - + a *"
--------------------------------------------
Expect error: For the infix expression "11+", the Polish expression or
error report is

Error detected at or near character 3 in "11+": Addition or
subtraction operator is not followed by addFactor
--------------------------------------------
Expect error: For the infix expression "11 +", the Polish expression
or error report is

Error detected at or near character 2 in "11 +": Expected addition or
subtraction operator not found
--------------------------------------------
Expect "10 113 + a *": For the infix expression "(10+113)*a", the
Polish expression or error report is

10 113 + a *
--------------------------------------------
Expect "10 113 + a *": For the infix expression "((10+113))*a", the
Polish expression or error report is

10 113 + a *
--------------------------------------------
Expect "1": For the infix expression "1", the Polish expression or
error report is

1
--------------------------------------------
Expect "a b + c -": For the infix expression "a+b-c", the Polish
expression or error report is

a b + c -
--------------------------------------------
Expect "1 1 +": For the infix expression "1+1", the Polish expression
or error report is

1 1 +
--------------------------------------------




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()
{
string strSep =
Environment.NewLine +
"--------------------------------------------" +
Environment.NewLine;
return "Expect \"\": " +
infix2PolishTest("") +
strSep +
"Expect \"\": " +
infix2PolishTest(" ") +
strSep +
"Expect \"2 4 3 + /\": " +
infix2PolishTest("2/(4+3)") +
strSep +
"Expect \"2 4 / 3 +\": " +
infix2PolishTest("2/4+3") +
strSep +
"Expect \"2 4 3 + /\": " +
infix2PolishTest("((2/(4+3)))") +
strSep +
"Expect " +
"\"10 113 2 2 4 3 + / + 2 + 2 " +
"+ - + a *\": " +
infix2PolishTest
("((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a") +
"\"" +
strSep +
"Expect error: " +
infix2PolishTest("11+") +
strSep +
"Expect error: " +
infix2PolishTest("11 +") +
strSep +
"Expect \"10 113 + a *\": " +
infix2PolishTest("(10+113)*a") +
strSep +
"Expect \"10 113 + a *\": " +
infix2PolishTest("((10+113))*a") +
strSep +
"Expect \"1\": " +
infix2PolishTest("1")+
strSep +
"Expect \"a b + c -\": " +
infix2PolishTest("a+b-c") +
strSep +
"Expect \"1 1 +\": " +
infix2PolishTest("1+1") +
strSep;
}

private static string infix2PolishTest(string strInfix)
{
return "For the infix expression " +
"\"" + strInfix + "\", " +
"the Polish expression or error report is " +
Environment.NewLine +
Environment.NewLine +
infix2Polish(strInfix);
}

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 (intIndex > intEnd) return false;
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++;
}
else
return errorHandler(strInfix,
intIndex,
ref strErrorMessage,
"Unexpected character " +
"'" + strInfix[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;
}
}
}
 
S

spinoza1111

Since Ben is too lazy and too discourteous to reply with errors, I
shall reply with errors in the code that I found when starting to
convert it to C.

Briefly it failed for a null string and a blank.

It failed (out of bounds subscript) in the mulFactor recognizer when
the infix expression was a null string. This is because mulFactor is
what would be in a more elaborate parser a lexxer looking to the next
character and returning some agreed on symbol when the input is at an
end. Therefore, mulFactor has to take responsibility in the absence of
a lexxer for detailed pointer checks. It started by looking for a
letter without  checking intIndex for being out of bounds.

It needed this check. The second test in mulFactor did not since the
bounds check is part of the while condition. But the third test for a
left parenthesis also needed this check.

I put a new check at the start of mulFactor, returning false when
intIndex>intEnd. I also added a false and error return when mulFactor,
which again combines the jobs of mulFactor and lex, fails to find one
of its three alternatives: letter, number, parenthesized expression. I
also made the output of the regression test more readable.

Note that people who make mistakes learn more even if like Knuth wrt
binary search they make them more than once, IF they are not
constantly interrupted by autistic twerps. They also teach more.

There may have been other mistakes in this code. I have neither
formally nor informally proved it correct. But apart from making an
unsupported claim, Bacarisse has as yet provided no insights. I have
had to do so, so far, wrt to the null string and blank character bug.

Nothing could more clearly indicate the pathology of a newsgroup so
dominated by autistic twerps.

Here is the new test regression output, followed by the new code.

Expect "": For the infix expression "", the Polish expression or error
report is

One nit: it shouldn't say here and on the next line "expect a null
string": it should say "expect an error".

I will take Peter's and Richard's silence on these posts to indicate
incompetence to study this code and find flaws.

I shall take Ben's as indicating that he's out Trick or Treating, or
is studying the code desparate to find a justification for his slander.
 
S

Seebs

I will take Peter's and Richard's silence on these posts to indicate
incompetence to study this code and find flaws.

I don't know the language you wrote it in, and also don't feel a lot of
need to try to find flaws in your code.

Write something in a language I know and post it in an appropriate group
and I'd be glad to critique it for you. My interest level in learning
C# is pretty low to begin with, and trying to learn it just to critique
your code seems particularly pointless.

-s
 
S

spinoza1111

I don't know the language you wrote it in, and also don't feel a lot of
need to try to find flaws in your code.

Write something in a language I know and post it in an appropriate group
and I'd be glad to critique it for you.  My interest level in learning
C# is pretty low to begin with, and trying to learn it just to critique
your code seems particularly pointless.

I have written it in C# as a way to prototype it for the original
poster without doing his homework for him, and now that he's probably
handed in the assignment, I am rewriting it in C, using the C Sharp as
a prototype.

Furthermore, I have taken the risk of critiqueing C without being, any
more, completely familiar with the language. I submit that you're
afraid that I will laugh at you should you critique C Sharp. Fear not.
I am no autistic twerp.

The original intent of programming language design on the part of
Grace Hopper, John Backus, Edsger Dijkstra and the men who created
Algol was NOT to create a group of mutually incomprehensible tribal
languages and a bunch of phony "experts". Therefore, real computer
scientists are willing to comment on code in unfamiliar languages, for
essentially the same reason that in a humanistic structured
walkthrough, contributions from all members are encouraged, and any
"pecking order", especially some pecking order dominated by autistic
twerps, where the savagery is complementary to the savagery with which
some of these twerps were treated growing up, is discouraged.

Can you write it in C using my C Sharp as a prototype, given that C
Sharp is broadly similar to C?
 
S

spinoza1111

I don't know the language you wrote it in, and also don't feel a lot of
need to try to find flaws in your code.

Write something in a language I know and post it in an appropriate group

Furthermore, the idea that computer languages are even distinct is
absurd. That they are is a historical accident, caused by the large
number of errors made in language design in the early days.

Insofar as "knowledge" of C is knowledge of mistakes, C has no
standing as an academic subject and should not be spoken of as a
computer language. Instead, it should be considered a pathology which
computer scientists must learn for the same reason doctors must learn
cancer.

People whose main claim to expertise in C should be sent to re-
education camps on the model of UN centres in Africa which train
former guerrillas in useful trades.

And the world still needs one programming language that can be used by
everyone. The guy on the screen in the 1984 Apple commercial was
right.
 
S

Seebs

Furthermore, I have taken the risk of critiqueing C without being, any
more, completely familiar with the language. I submit that you're
afraid that I will laugh at you should you critique C Sharp. Fear not.
I am no autistic twerp.

It's not that, it's that I don't know the language and wouldn't care to
try to criticize code in a language I don't know. You're welcome to laugh
at me anyway if you wish. It may help if you imagine that I've got a big
red clown nose. Honk honk! Honk honk!
The original intent of programming language design on the part of
Grace Hopper, John Backus, Edsger Dijkstra and the men who created
Algol

Your name-dropping is starting to make me wonder if it's NPD week in
comp.lang.c. Why do you obsessively cite to other people's accomplishments?
was NOT to create a group of mutually incomprehensible tribal
languages and a bunch of phony "experts".

Doubtless it wasn't.
Therefore, real computer
scientists are willing to comment on code in unfamiliar languages,

Ahh. I see. The intent of the people who developed natural human language
was not to create a group of mutually incomprehensible tribal languages
and a bunch of phony "experts", which is why real linguists are willing to
review books in unfamiliar languages.

Furthermore, it's worth pointing out that C# was not created by the
luminaries of the field, but rather by Microsoft, and that their history
strongly suggests that it was *exactly* their intent to create a tribal
language mutually-incomprehensible with other languages and a bunch of
phony "experts", because that's been their strategy throughout the
last thirty or so years.
for
essentially the same reason that in a humanistic structured
walkthrough, contributions from all members are encouraged, and any
"pecking order", especially some pecking order dominated by autistic
twerps, where the savagery is complementary to the savagery with which
some of these twerps were treated growing up, is discouraged.

This is a beautiful example of the kind of rant that keeps us coming back
to your posts. I'm sufficiently free of pecking orders that it's considered
a neurological disorder, and you're ranting at me about pecking orders.
That's amusing.

But it doesn't change the fact that I don't know C#, and have pretty much
no interest in reviewing hundreds of lines of non-C code in comp.lang.c. I
would react the same way to a suggestion that I review a ton of shell
script code here, even though I consider myself basically competent to
review shell scripts.
Can you write it in C using my C Sharp as a prototype, given that C
Sharp is broadly similar to C?

I probably could, but I don't see why I'd bother. I can write C code
from all sorts of stuff, but this seems like fundamentally dull code.
Pick something fun!

-s
 
S

Seebs

Furthermore, the idea that computer languages are even distinct is
absurd. That they are is a historical accident, caused by the large
number of errors made in language design in the early days.

Hmm. You should hook up with Scott Nudds, I'm sure he'd appreciate your
insights into the merits of language design.

I don't think I find your argument persuasive. I do not think there exists
a universally ideal language design; in fact, it seems to me that
domain-specific languages are a compelling choice for many applications.

I view languages as tools. I expect to see a single unified language
about the time I expect to see a single unified woodworking tool, and
for about the same reasons.
Insofar as "knowledge" of C is knowledge of mistakes,

Except you've never shown this. You've asserted that it fails to conform
to your expectations, and that you think this is a mistake, but you've not
exactly proven your point.
C has no
standing as an academic subject and should not be spoken of as a
computer language. Instead, it should be considered a pathology which
computer scientists must learn for the same reason doctors must learn
cancer.

That's a whole lot of very pretty rhetoric, but again, you have to prove
your point before arguing further from it.
People whose main claim to expertise in C should be sent to re-
education camps on the model of UN centres in Africa which train
former guerrillas in useful trades.

This isn't a sentence, but if it were, I'd bet it would be a stupid
one. You seem to have omitted a clause, though. Anyway, don't worry,
I'm almost certainly more famous for expertise in Bourne shell than
I am for expertise in C now. (And if you want to see a language which
is chock full of astounding mistakes, Bourne shell is a true marvel
of the art. It isn't used because it's an incredibly well-designed
language, but because it's extremely widely available and fairly
flexible, and we've learned how to overcome most of the weaknesses.)
And the world still needs one programming language that can be used by
everyone. The guy on the screen in the 1984 Apple commercial was
right.

You know, it's a shame that we wasted thousands and thousands of years
of peoples' time researching computer science and language design when we
coulda just watched a superbowl ad and gotten the real answer.

Tell you what, just as a quick sanity check:

The one programming language that can be used by everyone:
* Should have a way to express explicit invocation of specific machine
instructions, yes/no?
* Should completely abstract away memory management so there's no such
things as pointers, yes/no?
* Should be designed for "intelligent" people rather than "autistic twerps",
yes/no?
* Should be accessible to people who are not particularly intelligent,
yes/no?
* Should compile directly to machine-specific instructions, yes/no?
* Should be interpreted dynamically and allow for the evaluation of
strings of text, yes/no?

I'm really looking forward to your answers.

-s
 
S

Seebs

No, he's banging on about the C++ version, which is similarly riddled.
Linky?

2. (b) - sizeof "hello world" != sizeof(char *) EORWS. The setter may
expect (a) - it's another common misconception.

My quibble: A string is not "equivalent to a pointer to character".
A string is a series of bytes terminated by a null byte.
4. (b) - str cannot be a character pointer variable that holds a
string, but if it points to that string, str[3] has the value 'd',
not 'a'. One would hope that the setter knows this.

In a fit of inspired brilliance, I actually got that one wrong.
It is not every day I can be tripped up by the fencepost.
6. (b) - C doesn't have pass by reference, so addresses of variables
can't be passed by reference. The setter may expect (a) - it's a
common misconception.

Yes, exactly.
9. (b) - I suspect that vTrue is a typo for True, but in any case it's
false so that's fine. Unless the setter doesn't know about the dot
operator, of course.

I went with "false", because, as you note, you can't use -> on a struct,
only on a pointer-to-struct.
11. (d) - but they mean '\0', not '\\0'
Uh-huh.

14. (a) is (probably) the intended answer, but the real answer is that
the behaviour of the program is undefined because it calls a variadic
function without a valid prototype in scope.
Heh.

17. (d) is undoubtedly the intended answer. In C, the value of NULL is
always 0. Its type is either int or void *.

I love this question. "In most languages..." Uh, lolwut?

Also, while 0x00000000 is indeed a value which compares equal to NULL,
it's not necessarily a reasonable guess as to the value NULL has. But
it's a likely output from, say, trying to print a null pointer with %p.
But... most *languages*?
25. (a) is probably (and ought to be) the intended answer; for
example, int p[6]; *p = 42; - of course, there are situations in
which an array /cannot/ be used as a constant pointer. For example:
int arr[32]; int *p = arr; size_t s1 = sizeof arr; s2 = sizeof p;
will give different values for s1 and s2 (EORWS).

Yeah. I feel that an array really can't be used as a constant pointer,
because (e.g.) it has the wrong size, etcetera.
26. (d) is intended, but should say "any of the above" since it
clearly can't hold all of them at once (unions notwithstanding).

Pointers as a class can store all, so I think it's okay.
29. (d) is the expected answer, but the real answer is that the
behaviour of the code is undefined.
Yup.

34. (c) is the intended answer. Also, the cast is pointless.

But possibly there to throw you off.
43. (d) is the correct answer - argv is actually a pointer to pointer
to char, which points at the first element of an array of strings. It
is not clear what answer is intended, however.

I think they want "array of arrays of characters". But it's not, because
an array of arrays of characters would have to specify the size of the
sub-arrays.
The answering mechanism gave incorrect responses to several of these
questions, of which Q42 is the most embarrassing - it wants 10, where
the answer is quite obviously 9. I can think of no reasonable
circumstance in which any competent C programmer could possibly
imagine that 10 is a correct answer to that question.

Yeah. That was the one that really stood out for me as being Just Plain
Dumb.

-s
 
S

Seebs

The problem is that if a question is at all interesting it will have more
than one answer. Sure, you can ask, "which construct is portable?". However
the assumption that C bytes are 8 bits is probably more portable than the
assumption that a long is at least 32 bits. 8 bit bytes are so useful that
compiler writers fake them up even when the underlying hardware won't
support the reads, even though the standard doesn't require this. Whilst on
tiny systems int is sometimes 8 bits and long 16 bits, to encourage
programmers to use integers that fit in registers where possible. So to
answer a question about "portability" you need to explain the situation.
Which won't fit in atick box.

Obviously, nothing with I8L16 has complied with any C standard, but perhaps
you could identify an example of any machine ever, anywhere, which has
implemented C in such a way?

I can't imagine it. The convenient existence of char and short for small
objects makes it seem awfully strange to imagine anyone implementing that.

-s
 
S

Seebs

One system I used had 8 bit ints. It was a tiny 4K embedded chip, and it was
intended to run a parking ticket meter. (In the event a rival company got
the job, but not before we'd looked at the system to prepare our tender).

Weird. I could imagine someone just punting and saying "we can't even
pretend to implement C, here's a stripped down system with nothing supported",
but I can't imagine someone calling a system with 8-bit ints "C". What
year was this about?

-s
 
N

Nick Keighley

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.

"Gresham's law is commonly stated: "Bad money drives out good""

"Sturgeon's Law. “Ninety percent of everything is crud.”"
 
B

Ben Bacarisse

spinoza1111 said:
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.

The evidence of the first is the truth of the second. The evidence
for the second is the code you posted. The set of strings that it
accepts is not a mystery. Whether that set is the same as the
language defined by the grammar is simple matter of fact. All the
evidence is there.

What you mean, I think, is that I am not being helpful enough. You
don't want to take the time to understand or test your code and you'd
like me to help more. If you want help writing a recursive descent
parser, post a question in a group where it is topical. If you want
help with you C#, post in a C# group. The details are off topic here.

You are probably correct about the last point: I may never have seen
that particular algorithm. There are lots of incorrect parsing
algorithms and despite having seen, literally, hundreds of students
try to do what you tried, I may well never have seen that particular
version.
 
S

spinoza1111

In <[email protected]>,

spinoza1111wrote:



How kind. In return, I will take your failure to present evidence,
when asked, of any specific claim you make as your acceptance that
that specific claim is false. Which makes the vast, vast, vast vast
vast majority of your claims false.

You're silly bastard.

You see, in practically every post you mention my "errors" in the same
way people prefer to repeat "the errors of Schildt" as if this cite of
a cite makes the errors more numerous.
 
S

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.

Since Ben is too lazy and too discourteous to reply with errors, I
shall reply with errors in the code that I found when starting to
convert it to C.

Briefly it failed for a null string and a blank.

It failed (out of bounds subscript) in the mulFactor recognizer when
the infix expression was a null string. This is because mulFactor is
what would be in a more elaborate parser a lexxer looking to the next
character and returning some agreed on symbol when the input is at an
end. Therefore, mulFactor has to take responsibility in the absence of
a lexxer for detailed pointer checks. It started by looking for a
letter without  checking intIndex for being out of bounds.

It needed this check. The second test in mulFactor did not since the
bounds check is part of the while condition. But the third test for a
left parenthesis also needed this check.

I put a new check at the start of mulFactor, returning false when
intIndex>intEnd. I also added a false and error return when mulFactor,
which again combines the jobs of mulFactor and lex, fails to find one
of its three alternatives: letter, number, parenthesized expression. I
also made the output of the regression test more readable.

Note that people who make mistakes learn more even if like Knuth wrt
binary search they make them more than once, IF they are not
constantly interrupted by autistic twerps. They also teach more.

There may have been other mistakes in this code. I have neither
formally nor informally proved it correct. But apart from making an
unsupported claim, Bacarisse has as yet provided no insights. I have
had to do so, so far, wrt to the null string and blank character bug.

Nothing could more clearly indicate the pathology of a newsgroup so
dominated by autistic twerps.

Here is the new test regression output, followed by the new code.

Expect "": For the infix expression "", the Polish expression or error
report is

Error detected at or near character 0 in "": Expected multiplication
factor not found; Error detected at or near character 0 in "":
Expression doesn't start with addFactor
--------------------------------------------
Expect "": For the infix expression " ", the Polish expression or
error report is

Error detected at or near character 0 in " ": Unexpected character '
'; Error detected at or near character 0 in " ": Expected
multiplication factor not found; Error detected at or near character 0
in " ": Expression doesn't start with addFactor
--------------------------------------------
Expect "2 4 3 + /": For the infix expression "2/(4+3)", the Polish
expression or error report is

2 4 3 + /
--------------------------------------------
Expect "2 4 / 3 +": For the infix expression "2/4+3", the Polish
expression or error report is

2 4 / 3 +
--------------------------------------------
Expect "2 4 3 + /": For the infix expression "((2/(4+3)))", the Polish
expression or error report is

2 4 3 + /
--------------------------------------------
Expect "10 113 2 2 4 3 + / + 2 + 2 + - + a *": For the infix
expression "((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a", the Polish
expression or error report is

10 113 2 2 4 3 + / + 2 + 2 + - + a *"
--------------------------------------------
Expect error: For the infix expression "11+", the Polish expression or
error report is

Error detected at or near character 3 in "11+": Addition or
subtraction operator is not followed by addFactor
--------------------------------------------
Expect error: For the infix expression "11 +", the Polish expression
or error report is

Error detected at or near character 2 in "11 +": Expected addition or
subtraction operator not found
--------------------------------------------
Expect "10 113 + a *": For the infix expression "(10+113)*a", the
Polish expression or error report is

10 113 + a *
--------------------------------------------
Expect "10 113 + a *": For the infix expression "((10+113))*a", the
Polish expression or error report is

10 113 + a *
--------------------------------------------
Expect "1": For the infix expression "1", the Polish expression or
error report is

1
--------------------------------------------
Expect "a b + c -": For the infix expression "a+b-c", the Polish
expression or error report is

a b + c -
--------------------------------------------
Expect "1 1 +": For the infix expression "1+1", the Polish expression
or error report is

1 1 +
--------------------------------------------

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()
        {
            string strSep =
                   Environment.NewLine +
                   "--------------------------------------------" +
                   Environment.NewLine;
            return "Expect \"\": " +
                   infix2PolishTest("") +
                   strSep +
                   "Expect \"\": " +
                   infix2PolishTest(" ") +
                   strSep +
                   "Expect \"2 4 3 + /\": " +
                   infix2PolishTest("2/(4+3)") +
                   strSep +
                   "Expect \"2 4 / 3 +\": "  +
                   infix2PolishTest("2/4+3") +
                   strSep +
                   "Expect \"2 4 3 + /\": " +
                   infix2PolishTest("((2/(4+3)))") +
                   strSep +
                   "Expect " +
                   "\"10 113 2 2 4 3 + / + 2 + 2 " +
                   "+ - + a *\": " +
                   infix2PolishTest
                   ("((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a") +
                   "\"" +
                   strSep +
                   "Expect error: " +
                   infix2PolishTest("11+") +
                   strSep +
                   "Expect error: " +
                   infix2PolishTest("11 +") +
                   strSep +
                   "Expect \"10 113 + a *\": " +
                   infix2PolishTest("(10+113)*a") +
                   strSep +
                   "Expect \"10 113 + a *\": " +
                   infix2PolishTest("((10+113))*a") +
                   strSep +
                   "Expect \"1\": " +
                   infix2PolishTest("1")+
                   strSep +
                   "Expect \"a b + c -\": " +
                   infix2PolishTest("a+b-c") +
                   strSep +
                   "Expect \"1 1 +\": " +
                   infix2PolishTest("1+1") +
                   strSep;
        }

        private static string infix2PolishTest(string strInfix)
        {
            return "For the infix expression " +
                   "\"" + strInfix + "\", " +
                   "the Polish expression or error report is " +
                   Environment.NewLine +
                   Environment.NewLine +
                   infix2Polish(strInfix);
        }

        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

read more »- Hide quoted text -

- Show quoted text -...

Ben Bacarisse sent me email identifying what he considered several
problems:

1. "(" : produced he said an invalid array reference
2. "////2": failed he said
3. "((((2" produced he said the Polish expression 2
4. "(": failed he said
5. "()" failed he said
6. "+" failed, he said

I added each case to the regression tests in tester() and only ((((2
failed, producing without error the Polish expression 2. 1, and 3-5
all work with the most recent version of the program which corrected
failures to test end of expression.

I have, in the latest version below (following the output of the
latest regression test), added an error call before the "exit:" label
that is the target of a go to (eek!) when intLevel is zero on the
detection of right parenthesis. If the loop that balances the
parentheses fails to match it will exit and this error will be caught.

Ben said the code was roundabout, and he doesn't seem to like the
"lookahead" strategy that finds matching parentheses. It uses a go to
(eek) which is unnecessary and can be replaced by an extra test on
exit from the balancing loop (if intIndex>intEnd, then parentheses do
not balance, otherwise call expression() recursively).

An alternative would be to treat end of string as a separate grammar
symbol, I believe, although I have not worked this strategy out in
detail.

Ben's use of email to identify errors saves a lot of pibble pabble
back and forth and I recommend it.

Here is the latest regression test, followed by the latest code.


Expect error: For the infix expression "(", the Polish expression or
error report is

Error detected at or near character 1 in "(": Parentheses are not
balanced; Error detected at or near character 1 in "(": Expected
multiplication factor not found; Error detected at or near character 1
in "(": Expression doesn't start with addFactor
--------------------------------------------
Expect error: For the infix expression "////2", the Polish expression
or error report is

Error detected at or near character 0 in "////2": Unexpected character
'/'; Error detected at or near character 0 in "////2": Expected
multiplication factor not found; Error detected at or near character 0
in "////2": Expression doesn't start with addFactor
--------------------------------------------
Expect error: For the infix expression "((((2", the Polish expression
or error report is

Error detected at or near character 1 in "((((2": Parentheses are not
balanced; Error detected at or near character 1 in "((((2": Expected
multiplication factor not found; Error detected at or near character 1
in "((((2": Expression doesn't start with addFactor
--------------------------------------------
Expect error: For the infix expression "()", the Polish expression or
error report is

Error detected at or near character 1 in "()": Expected multiplication
factor not found; Error detected at or near character 1 in "()":
Expression doesn't start with addFactor; Error detected at or near
character 1 in "()": Nested expression invalid; Error detected at or
near character 1 in "()": Expected multiplication factor not found;
Error detected at or near character 1 in "()": Expression doesn't
start with addFactor
--------------------------------------------
Expect error: For the infix expression "+", the Polish expression or
error report is

Error detected at or near character 0 in "+": Unexpected character
'+'; Error detected at or near character 0 in "+": Expected
multiplication factor not found; Error detected at or near character 0
in "+": Expression doesn't start with addFactor
--------------------------------------------
Expect "": For the infix expression "", the Polish expression or error
report is

Error detected at or near character 0 in "": Expected multiplication
factor not found; Error detected at or near character 0 in "":
Expression doesn't start with addFactor
--------------------------------------------
Expect "": For the infix expression " ", the Polish expression or
error report is

Error detected at or near character 0 in " ": Unexpected character '
'; Error detected at or near character 0 in " ": Expected
multiplication factor not found; Error detected at or near character 0
in " ": Expression doesn't start with addFactor
--------------------------------------------
Expect "2 4 3 + /": For the infix expression "2/(4+3)", the Polish
expression or error report is

2 4 3 + /
--------------------------------------------
Expect "2 4 / 3 +": For the infix expression "2/4+3", the Polish
expression or error report is

2 4 / 3 +
--------------------------------------------
Expect "2 4 3 + /": For the infix expression "((2/(4+3)))", the Polish
expression or error report is

2 4 3 + /
--------------------------------------------
Expect "10 113 2 2 4 3 + / + 2 + 2 + - + a *": For the infix
expression "((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a", the Polish
expression or error report is

10 113 2 2 4 3 + / + 2 + 2 + - + a *"
--------------------------------------------
Expect error: For the infix expression "11+", the Polish expression or
error report is

Error detected at or near character 3 in "11+": Addition or
subtraction operator is not followed by addFactor
--------------------------------------------
Expect error: For the infix expression "11 +", the Polish expression
or error report is

Error detected at or near character 2 in "11 +": Expected addition or
subtraction operator not found
--------------------------------------------
Expect "10 113 + a *": For the infix expression "(10+113)*a", the
Polish expression or error report is

10 113 + a *
--------------------------------------------
Expect "10 113 + a *": For the infix expression "((10+113))*a", the
Polish expression or error report is

10 113 + a *
--------------------------------------------
Expect "1": For the infix expression "1", the Polish expression or
error report is

1
--------------------------------------------
Expect "a b + c -": For the infix expression "a+b-c", the Polish
expression or error report is

a b + c -
--------------------------------------------
Expect "1 1 +": For the infix expression "1+1", the Polish expression
or error report is

1 1 +
--------------------------------------------


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()
{
string strSep =
Environment.NewLine +
"--------------------------------------------" +
Environment.NewLine;
return "Expect error: " +
infix2PolishTest("(") +
strSep +
"Expect error: " +
infix2PolishTest("////2") +
strSep +
"Expect error: " +
infix2PolishTest("((((2") +
strSep +
"Expect error: " +
infix2PolishTest("()") +
strSep +
"Expect error: " +
infix2PolishTest("+") +
strSep +
"Expect \"\": " +
infix2PolishTest("") +
strSep +
"Expect \"\": " +
infix2PolishTest(" ") +
strSep +
"Expect \"2 4 3 + /\": " +
infix2PolishTest("2/(4+3)") +
strSep +
"Expect \"2 4 / 3 +\": " +
infix2PolishTest("2/4+3") +
strSep +
"Expect \"2 4 3 + /\": " +
infix2PolishTest("((2/(4+3)))") +
strSep +
"Expect " +
"\"10 113 2 2 4 3 + / + 2 + 2 " +
"+ - + a *\": " +
infix2PolishTest
("((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a") +
"\"" +
strSep +
"Expect error: " +
infix2PolishTest("11+") +
strSep +
"Expect error: " +
infix2PolishTest("11 +") +
strSep +
"Expect \"10 113 + a *\": " +
infix2PolishTest("(10+113)*a") +
strSep +
"Expect \"10 113 + a *\": " +
infix2PolishTest("((10+113))*a") +
strSep +
"Expect \"1\": " +
infix2PolishTest("1")+
strSep +
"Expect \"a b + c -\": " +
infix2PolishTest("a+b-c") +
strSep +
"Expect \"1 1 +\": " +
infix2PolishTest("1+1") +
strSep;
}

private static string infix2PolishTest(string strInfix)
{
return "For the infix expression " +
"\"" + strInfix + "\", " +
"the Polish expression or error report is " +
Environment.NewLine +
Environment.NewLine +
infix2Polish(strInfix);
}

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 (intIndex > intEnd) return false;
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;
}
}
return errorHandler
(strInfix,
intIndex,
ref strErrorMessage,
"Parentheses are not balanced");
exit:
if (!expression(strInfix,
ref strPolish,
ref intIndex,
ref strErrorMessage,
intIndexAhead - 1))
return errorHandler
(strInfix,
intIndex,
ref strErrorMessage,
"Nested expression invalid");
intIndex++;
}
else
return errorHandler(strInfix,
intIndex,
ref strErrorMessage,
"Unexpected character " +
"'" + strInfix[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;
}
}
}
 
S

spinoza1111

THIS POST JUST CONTAINS THE LATEST CODE AND REGRESSION TEST, WHICH
ADDRESS ALL OF BEN'S CONCERNS

spinoza1111<[email protected]> writes:

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.


Since Ben is too lazy and too discourteous to reply with errors, I
shall reply with errors in the code that I found when starting to
convert it to C.

Briefly it failed for a null string and a blank.

It failed (out of bounds subscript) in the mulFactor recognizer when
the infix expression was a null string. This is because mulFactor is
what would be in a more elaborate parser a lexxer looking to the next
character and returning some agreed on symbol when the input is at an
end. Therefore, mulFactor has to take responsibility in the absence of
a lexxer for detailed pointer checks. It started by looking for a
letter without checking intIndex for being out of bounds.

It needed this check. The second test in mulFactor did not since the
bounds check is part of the while condition. But the third test for a
left parenthesis also needed this check.

I put a new check at the start of mulFactor, returning false when
intIndex>intEnd. I also added a false and error return when mulFactor,
which again combines the jobs of mulFactor and lex, fails to find one
of its three alternatives: letter, number, parenthesized expression. I
also made the output of the regression test more readable.

Note that people who make mistakes learn more even if like Knuth wrt
binary search they make them more than once, IF they are not
constantly interrupted by autistic twerps. They also teach more.

There may have been other mistakes in this code. I have neither
formally nor informally proved it correct. But apart from making an
unsupported claim, Bacarisse has as yet provided no insights. I have
had to do so, so far, wrt to the null string and blank character bug.

Nothing could more clearly indicate the pathology of a newsgroup so
dominated by autistic twerps.

Here is the new test regression output, followed by the new code.

Expect "": For the infix expression "", the Polish expression or error
report is

Error detected at or near character 0 in "": Expected multiplication
factor not found; Error detected at or near character 0 in "":
Expression doesn't start with addFactor
--------------------------------------------
Expect "": For the infix expression " ", the Polish expression or
error report is

Error detected at or near character 0 in " ": Unexpected character '
'; Error detected at or near character 0 in " ": Expected
multiplication factor not found; Error detected at or near character 0
in " ": Expression doesn't start with addFactor
--------------------------------------------
Expect "2 4 3 + /": For the infix expression "2/(4+3)", the Polish
expression or error report is

2 4 3 + /
--------------------------------------------
Expect "2 4 / 3 +": For the infix expression "2/4+3", the Polish
expression or error report is

2 4 / 3 +
--------------------------------------------
Expect "2 4 3 + /": For the infix expression "((2/(4+3)))", the Polish
expression or error report is

2 4 3 + /
--------------------------------------------
Expect "10 113 2 2 4 3 + / + 2 + 2 + - + a *": For the infix
expression "((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a", the Polish
expression or error report is

10 113 2 2 4 3 + / + 2 + 2 + - + a *"
--------------------------------------------
Expect error: For the infix expression "11+", the Polish expression or
error report is

Error detected at or near character 3 in "11+": Addition or
subtraction operator is not followed by addFactor
--------------------------------------------
Expect error: For the infix expression "11 +", the Polish expression
or error report is

Error detected at or near character 2 in "11 +": Expected addition or
subtraction operator not found
--------------------------------------------
Expect "10 113 + a *": For the infix expression "(10+113)*a", the
Polish expression or error report is

10 113 + a *
--------------------------------------------
Expect "10 113 + a *": For the infix expression "((10+113))*a", the
Polish expression or error report is

10 113 + a *
--------------------------------------------
Expect "1": For the infix expression "1", the Polish expression or
error report is

1
--------------------------------------------
Expect "a b + c -": For the infix expression "a+b-c", the Polish
expression or error report is

a b + c -
--------------------------------------------
Expect "1 1 +": For the infix expression "1+1", the Polish expression
or error report is

1 1 +
--------------------------------------------

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()
{
string strSep =
Environment.NewLine +
"--------------------------------------------" +
Environment.NewLine;
return "Expect \"\": " +
infix2PolishTest("") +
strSep +
"Expect \"\": " +
infix2PolishTest(" ") +
strSep +
"Expect \"2 4 3 + /\": " +
infix2PolishTest("2/(4+3)") +
strSep +
"Expect \"2 4 / 3 +\": " +
infix2PolishTest("2/4+3") +
strSep +
"Expect \"2 4 3 + /\": " +
infix2PolishTest("((2/(4+3)))") +
strSep +
"Expect " +
"\"10 113 2 2 4 3 + / + 2 + 2 " +
"+ - + a *\": " +
infix2PolishTest
("((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a") +
"\"" +
strSep +
"Expect error: " +
infix2PolishTest("11+") +
strSep +
"Expect error: " +
infix2PolishTest("11 +") +
strSep +
"Expect \"10 113 + a *\": " +
infix2PolishTest("(10+113)*a") +
strSep +
"Expect \"10 113 + a *\": " +
infix2PolishTest("((10+113))*a") +
strSep +
"Expect \"1\": " +
infix2PolishTest("1")+
strSep +
"Expect \"a b + c -\": " +
infix2PolishTest("a+b-c") +
strSep +
"Expect \"1 1 +\": " +
infix2PolishTest("1+1") +
strSep;
}

private static string infix2PolishTest(string strInfix)
{
return "For the infix expression " +
"\"" + strInfix + "\", " +
"the Polish expression or error report is " +
Environment.NewLine +
Environment.NewLine +
infix2Polish(strInfix);
}

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

read more »- Hide quoted text -

- Show quoted text -...



Ben Bacarisse sent me email identifying what he considered several
problems:

1. "(" : produced he said an invalid array reference
2. "////2": failed he said
3. "((((2" produced he said the Polish expression 2
4. "(": failed he said
5. "()" failed he said
6. "+" failed, he said


I added each case to the regression tests in tester() and only ((((2
failed, producing without error the Polish expression 2. 1, and 3-5
all work with the most recent version of the program which corrected
failures to test end of expression.


I have, in the latest version below (following the output of the
latest regression test), added an error call before the "exit:" label
that is the target of a go to (eek!) when intLevel is zero on the
detection of right parenthesis. If the loop that balances the
parentheses fails to match it will exit and this error will be
caught.


Ben said the code was roundabout, and he doesn't seem to like the
"lookahead" strategy that finds matching parentheses. It uses a go to
(eek) which is unnecessary and can be replaced by an extra test on
exit from the balancing loop (if intIndex>intEnd, then parentheses do
not balance, otherwise call expression() recursively).


An alternative would be to treat end of string as a separate grammar
symbol, I believe, although I have not worked this strategy out in
detail.


Ben's use of email to identify errors saves a lot of pibble pabble
back and forth and I recommend it.


Here is the latest regression test, followed by the latest code.


Expect error: For the infix expression "(", the Polish expression or
error report is


Error detected at or near character 1 in "(": Parentheses are not
balanced; Error detected at or near character 1 in "(": Expected
multiplication factor not found; Error detected at or near character
1
in "(": Expression doesn't start with addFactor
--------------------------------------------
Expect error: For the infix expression "////2", the Polish expression
or error report is


Error detected at or near character 0 in "////2": Unexpected
character
'/'; Error detected at or near character 0 in "////2": Expected
multiplication factor not found; Error detected at or near character
0
in "////2": Expression doesn't start with addFactor
--------------------------------------------
Expect error: For the infix expression "((((2", the Polish expression
or error report is


Error detected at or near character 1 in "((((2": Parentheses are not
balanced; Error detected at or near character 1 in "((((2": Expected
multiplication factor not found; Error detected at or near character
1
in "((((2": Expression doesn't start with addFactor
--------------------------------------------
Expect error: For the infix expression "()", the Polish expression or
error report is


Error detected at or near character 1 in "()": Expected
multiplication
factor not found; Error detected at or near character 1 in "()":
Expression doesn't start with addFactor; Error detected at or near
character 1 in "()": Nested expression invalid; Error detected at or
near character 1 in "()": Expected multiplication factor not found;
Error detected at or near character 1 in "()": Expression doesn't
start with addFactor
--------------------------------------------
Expect error: For the infix expression "+", the Polish expression or
error report is


Error detected at or near character 0 in "+": Unexpected character
'+'; Error detected at or near character 0 in "+": Expected
multiplication factor not found; Error detected at or near character
0
in "+": Expression doesn't start with addFactor
--------------------------------------------
Expect "": For the infix expression "", the Polish expression or
error
report is


Error detected at or near character 0 in "": Expected multiplication
factor not found; Error detected at or near character 0 in "":
Expression doesn't start with addFactor
--------------------------------------------
Expect "": For the infix expression " ", the Polish expression or
error report is


Error detected at or near character 0 in " ": Unexpected character '
'; Error detected at or near character 0 in " ": Expected
multiplication factor not found; Error detected at or near character
0
in " ": Expression doesn't start with addFactor
--------------------------------------------
Expect "2 4 3 + /": For the infix expression "2/(4+3)", the Polish
expression or error report is


2 4 3 + /
--------------------------------------------
Expect "2 4 / 3 +": For the infix expression "2/4+3", the Polish
expression or error report is


2 4 / 3 +
--------------------------------------------
Expect "2 4 3 + /": For the infix expression "((2/(4+3)))", the
Polish
expression or error report is


2 4 3 + /
--------------------------------------------
Expect "10 113 2 2 4 3 + / + 2 + 2 + - + a *": For the infix
expression "((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a", the Polish
expression or error report is


10 113 2 2 4 3 + / + 2 + 2 + - + a *"
--------------------------------------------
Expect error: For the infix expression "11+", the Polish expression
or
error report is


Error detected at or near character 3 in "11+": Addition or
subtraction operator is not followed by addFactor
--------------------------------------------
Expect error: For the infix expression "11 +", the Polish expression
or error report is


Error detected at or near character 2 in "11 +": Expected addition or
subtraction operator not found
--------------------------------------------
Expect "10 113 + a *": For the infix expression "(10+113)*a", the
Polish expression or error report is


10 113 + a *
--------------------------------------------
Expect "10 113 + a *": For the infix expression "((10+113))*a", the
Polish expression or error report is


10 113 + a *
--------------------------------------------
Expect "1": For the infix expression "1", the Polish expression or
error report is


1
--------------------------------------------
Expect "a b + c -": For the infix expression "a+b-c", the Polish
expression or error report is


a b + c -
--------------------------------------------
Expect "1 1 +": For the infix expression "1+1", the Polish expression
or error report is


1 1 +
--------------------------------------------


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()
{
string strSep =
Environment.NewLine +
"--------------------------------------------" +
Environment.NewLine;
return "Expect error: " +
infix2PolishTest("(") +
strSep +
"Expect error: " +
infix2PolishTest("////2") +
strSep +
"Expect error: " +
infix2PolishTest("((((2") +
strSep +
"Expect error: " +
infix2PolishTest("()") +
strSep +
"Expect error: " +
infix2PolishTest("+") +
strSep +
"Expect \"\": " +
infix2PolishTest("") +
strSep +
"Expect \"\": " +
infix2PolishTest(" ") +
strSep +
"Expect \"2 4 3 + /\": " +
infix2PolishTest("2/(4+3)") +
strSep +
"Expect \"2 4 / 3 +\": " +
infix2PolishTest("2/4+3") +
strSep +
"Expect \"2 4 3 + /\": " +
infix2PolishTest("((2/(4+3)))") +
strSep +
"Expect " +
"\"10 113 2 2 4 3 + / + 2 + 2 " +
"+ - + a *\": " +
infix2PolishTest
("((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a") +
"\"" +
strSep +
"Expect error: " +
infix2PolishTest("11+") +
strSep +
"Expect error: " +
infix2PolishTest("11 +") +
strSep +
"Expect \"10 113 + a *\": " +
infix2PolishTest("(10+113)*a") +
strSep +
"Expect \"10 113 + a *\": " +
infix2PolishTest("((10+113))*a") +
strSep +
"Expect \"1\": " +
infix2PolishTest("1")+
strSep +
"Expect \"a b + c -\": " +
infix2PolishTest("a+b-c") +
strSep +
"Expect \"1 1 +\": " +
infix2PolishTest("1+1") +
strSep;
}


private static string infix2PolishTest(string strInfix)
{
return "For the infix expression " +
"\"" + strInfix + "\", " +
"the Polish expression or error report is " +
Environment.NewLine +
Environment.NewLine +
infix2Polish(strInfix);
}


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 (intIndex > intEnd) return false;
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;
}
}
return errorHandler
(strInfix,
intIndex,
ref strErrorMessage,
"Parentheses are not balanced");
exit:
if (!expression(strInfix,
ref strPolish,
ref intIndex,
ref strErrorMessage,
intIndexAhead - 1))
return errorHandler
(strInfix,
intIndex,
ref strErrorMessage,
"Nested expression invalid");
intIndex++;
}
else
return errorHandler(strInfix,
intIndex,
ref strErrorMessage,
"Unexpected character " +
"'" + strInfix[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;
}
}


}
 
S

spinoza1111

The evidence of the first is the truth of the second.  The evidence
for the second is the code you posted.  The set of strings that it
accepts is not a mystery.  Whether that set is the same as the
language defined by the grammar is simple matter of fact.  All the
evidence is there.

What you mean, I think, is that I am not being helpful enough.  You
don't want to take the time to understand or test your code and you'd

Hey, asshole:

This is just absurd. I refer you to the effort I made to provide a
regression test. As a result, I have addressed EACH ISSUE you have
raised by email. Do me the courtesy of not enabling the jerks in this
ng and admitting this.
like me to help more.  If you want help writing a recursive descent

I wrote a book on doing this, but I of course need help as do we all
when we code, even in a language with which we're familiar, because,
as Dijsktra knew and you don't seem to, software is hard. When will
you learn this simple lesson?

Perhaps a new form of personality disorder exists in which one doesn't
make errors found by others, but if this is so, I see this ability
only in people with serious personality disorders. These may be an
artifact of overfocus on code, but in view of the damage they do to
both the people with these disorders and the targets of their vicious
little tirades, I don't think it's worth it...especially since we know
how, through the collegial and humane structured walkthrough from
which we exclude both managers and autistic twerps, to eradicate bugs.
parser, post a question in a group where it is topical.  If you want
help with you C#, post in a C# group.  The details are off topic here.

You are probably correct about the last point: I may never have seen
that particular algorithm.  There are lots of incorrect parsing
algorithms and despite having seen, literally, hundreds of students
try to do what you tried, I may well never have seen that particular
version.

It's not an incorrect algorithm. It's available in dozens of sources.
I CODED the algorithm (code isn't an algorithm) in a language in which
I'm familiar in a very limited amount of time, on the Lamma Island
ferry during a six day work week. To save time and add to ontopic
discussion, I posted the first version, which I knew probably had
bugs, for comment, since (for the last time, asshole), the OP was
supposed to write the C, not me. The C Sharp simply demonstrates how
the algorithm works.

You are welcome to find further problems. But stop acting like an
asshole in public. You are enabling the real assholes.
 
S

spinoza1111

AFAICT, you claim involvement dating to the mid 50's, so this should be easy
for you.  I'd like to see your list of the large number of errors in the
design of Algol 60.  As a matter of fact there *was* a very good language
available early on, but it never caught on in the USA; and the US, IBM and
Microsoft  has been dominant in the computer field for a very long time..

Dik has documented the fact that Algol's evaluation order was
nondeterministic. We now know that this is a mistake, since we now
know how to optimize.
 

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. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top