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;
}
}
}
(Hint: The last two are both