Among people I know, my best bet would probably be OS X or x86 Linux.
Many of my friends don't have any access at all to Windows.
It varies some.
-s
What ev er. Any way, here is the next version of the parser under
discussion, with input from you and Bacarisse. Try to make
constructive comments only. Thanks.
// ***************************************************************
// * *
// * infix2PolishC Infix to Polish notation using a grammar *
// * *
// * *
// * This application converts infix to Polish notation using a *
// * simple grammar and two different implementations. It also *
// * contains testing and timing facilities. For more *
// * information, see the readme.TXT file in this project. *
// * *
// * *
// * C H A N G E R E C O R D --------------------------------- *
// * DATE PROGRAMMER DESCRIPTION OF CHANGE *
// * -------- --------- --------------------------------- *
// * 11 01 09 Nilges Version 1 *
// * *
// * 11 03 09 Nilges Version 2 *
// * ANON 1. Commenting added DONE *
// * 2. Routine index added with *
// * forward definitions DONE *
// * 3. Expected/actual cleanup DONE *
// * 4. Bug? Seems to convert Polish *
// * expression to value of first *
// * token without complaint *
// * FIXED *
// * 5. Minor bug: extra spaces in *
// * polish expression FIXED *
// * 6. Bugs as found by anon *
// * 8.1 1) FIXED *
// * 8.2 (((1)))) FIXED *
// * 7. Predetermine malloc using *
// * number of symbols other than *
// * parentheses and white space *
// * *
// * 11 04 09 Nilges Version 3 *
// * 1. Predetermine malloc using *
// * infix length times two *
// * 2. Detab code for posting *
// * 3. Free polish expression after *
// * displaying it in testcase() *
// * as noticed by Seebs and *
// * recommended by Schildt *
// * 4. Display purpose of code on *
// * entry *
// * 5. Option to specify malloc on *
// * command line for Polish *
// * expression (primarily to test *
// * storage usage) *
// * *
// * I S S U E S ----------------------------------------------- *
// * DATE POSTER DESCRIPTION AND RESOLUTION *
// * -------- --------- --------------------------------- *
// * 11 03 09 Nilges Version 4 plan *
// * 1. Random expressions *
// * 2. Integrate in GUI with C sharp,*
// * versions from Gene, Seebach *
// * & anon *
// * 3. Post versions from Gene and *
// * Anon and Seebach version *
// * *
// ***************************************************************
#include <stdio.H>
#include <stdlib.H>
// ***** Constants ***********************************************
#define ABOUT_INFO \
"This application converts infix to Polish notation using a simple
grammar-based approach."
// ***** Macros **************************************************
// --- Pass over white space
#define SKIP_WHITE_SPACE(s, i, e) \
{ for(; (i) <= (e) && (s)[(i)] == ' '; (i)++ ); }
// --- Return maximum value
#define MAX(x, y) ((x) > (y) ? (x) : (y))
// ***** Function index ******************************************
#define ADDFACTOR \
int addFactor(char *strInfix, \
char *strPolish, \
int *intPtrIndex, \
int intEnd, \
int intMaxPolishLength)
ADDFACTOR;
#define ERRORHANDLER \
int errorHandler(char *strMessage)
ERRORHANDLER;
#define ERRORHANDLERSYNTAX \
int errorHandlerSyntax(int intIndex, \
char *strMessage, \
char *strInfix)
ERRORHANDLERSYNTAX;
#define EXPRESSION \
int expression(char *strInfix, \
char *strPolish, \
int *intPtrIndex, \
int intEnd, \
int intMaxPolishLength)
EXPRESSION;
#define FINDCHARS \
int findChars(char *strInstring, \
char *strFind, \
int intStartIndex)
FINDCHARS;
#define INFIX2POLISH \
int infix2Polish(char *strInfix, \
char *strPolish, \
int intMaxPolishLength)
INFIX2POLISH;
#define MAIN \
int main(int intArgCount, \
char *strArgs[])
MAIN;
#define MULFACTOR \
int mulFactor(char *strInfix, \
char *strPolish, \
int *intPtrIndex, \
int intEnd, \
int intMaxPolishLength)
MULFACTOR;
#define STRING2UNSIGNEDINT \
int string2UnsignedInt(char *strInstring)
STRING2UNSIGNEDINT;
#define STRINGAPPENDCHAR \
int stringAppendChar(char *strString, \
char chrNew, \
int intMaxLength, \
int intSpaceBefore)
STRINGAPPENDCHAR;
#define STRINGLENGTH \
int stringLength(char *strInstring)
STRINGLENGTH;
#define TESTCASE \
void testCase(char *strInfix, \
char *strExpected, \
int intMalloc)
TESTCASE;
#define TESTER \
void tester(int intMalloc)
TESTER;
// ***** Functions ***********************************************
// ---------------------------------------------------------------
// Command line handler
//
// int main(int intArgCount, char **strArgs)
//
MAIN
{
int intMalloc = -1;
printf("%s\n\n", ABOUT_INFO);
if (intArgCount > 1)
if ((intMalloc = string2UnsignedInt(strArgs[1])) < 0)
{
printf("%sInvalid malloc request %s\n", intMalloc);
return;
}
tester(intMalloc);
printf("\n\nTesting complete: check output for correctness");
return;
}
// ---------------------------------------------------------------
// Parse add factor
//
// int addFactor(char *strInfix,
// char *strPolish,
// int *intPtrIndex,
// int intEnd,
// int intMaxPolishLength)
//
// addFactor = mulFactor [ *|/ mulFactor ]
//
ADDFACTOR
{
char chrMulOp = ' ';
int intStartIndex = 0;
if (!mulFactor(strInfix,
strPolish,
intPtrIndex,
intEnd,
intMaxPolishLength))
{
errorHandlerSyntax(*intPtrIndex,
"mulFactor not found",
strInfix);
return 0;
}
if (*intPtrIndex > intEnd) return -1;
intStartIndex = *intPtrIndex;
while (1)
{
SKIP_WHITE_SPACE(strInfix, (*intPtrIndex), intEnd)
if (*intPtrIndex > intEnd) break;
if ((chrMulOp = strInfix[*intPtrIndex]) != '*'
&&
chrMulOp != '/')
return -1;
(*intPtrIndex)++;
if (*intPtrIndex > intEnd
||
!mulFactor(strInfix,
strPolish,
intPtrIndex,
intEnd,
intMaxPolishLength))
return errorHandlerSyntax
(*intPtrIndex,
"Mul/div op not followed by mulFactor",
strInfix);
if (!stringAppendChar(strPolish,
chrMulOp,
intMaxPolishLength,
1)) return 0;
}
return -1;
}
// ---------------------------------------------------------------
// Error handler
//
// int errorHandler(char *strMessage)
//
ERRORHANDLER
{
printf("\n%s\n", strMessage); return 0;
}
// ---------------------------------------------------------------
// Syntax error handler
//
// int errorHandlerSyntax(int intIndex,
// char *strMessage,
// char *strInfix)
//
ERRORHANDLERSYNTAX
{
int intIndex1 = 0;
printf("\nError at character %d: %s\n",
intIndex,
strMessage);
printf("%s\n", strInfix);
for (intIndex1 = 0; intIndex1 < intIndex; intIndex1++)
printf(" ");
printf("$");
return 0;
}
// ---------------------------------------------------------------
// Parse expression
//
// int expression(char *strInfix,
// char *strPolish,
// int *intPtrIndex,
// int intEnd,
// int intMaxPolishLength)
//
EXPRESSION
{ /* expression = addFactor [ +|- addFactor ] */
char chrAddOp = ' ';
int intStartIndex = 0;
if (!addFactor(strInfix,
strPolish,
intPtrIndex,
intEnd,
intMaxPolishLength))
{
errorHandlerSyntax(*intPtrIndex,
"addFactor not found",
strInfix);
return 0;
}
intStartIndex = *intPtrIndex;
while (1)
{
SKIP_WHITE_SPACE(strInfix, (*intPtrIndex), intEnd)
if (*intPtrIndex > intEnd) break;
if ((chrAddOp = strInfix[*intPtrIndex]) != '+'
&&
chrAddOp != '-')
return
errorHandlerSyntax
(*intPtrIndex,
"Unrecognizable char found instead of add op",
strInfix);
(*intPtrIndex)++;
if (*intPtrIndex > intEnd
||
!addFactor(strInfix,
strPolish,
intPtrIndex,
intEnd,
intMaxPolishLength))
return errorHandlerSyntax
(*intPtrIndex,
"Add/sub op not followed by addFactor",
strInfix);
stringAppendChar(strPolish,
chrAddOp,
intMaxPolishLength,
1);
}
return -1;
}
// ---------------------------------------------------------------
// Find one of a set of alternative characters
//
// int findChars(char *strInstring,
// char *strFind,
// int intStartIndex)
//
FINDCHARS
{
int intIndex1 = intStartIndex;
int intIndex2 = 0;
for (; strInstring[intIndex1] != '\0'; intIndex1++)
for (intIndex2 = 0;
strFind[intIndex2] != '\0';
intIndex2++)
if (strInstring[intIndex1] == strFind[intIndex2])
return intIndex1;
return intIndex1;
}
// ---------------------------------------------------------------
// Convert infix to Polish
//
// int infix2Polish(char *strInfix, int intMalloc)
//
INFIX2POLISH
{
int intIndex = 0;
int intLength = stringLength(strInfix);
strPolish[0] = '\0';
if (!expression(strInfix,
strPolish,
&intIndex,
intLength - 1,
intMaxPolishLength))
{
errorHandler("Error");
return 0;
}
return -1;
}
// ---------------------------------------------------------------
// Parse multiplication factor
//
// int mulFactor(char *strInfix,
// char *strPolish,
// int *intPtrIndex,
// int intEnd,
// int intMaxPolishLength)
//
// mulFactor = LETTER | NUMBER | '(' expression ')'
//
MULFACTOR
{
int intIndexStart = 0;
int intLevel = 0;
char chrNext = ' ';
int intInner = 0;
int intSpaceBefore = 0;
SKIP_WHITE_SPACE(strInfix, (*intPtrIndex), intEnd)
if (*intPtrIndex > intEnd)
return errorHandlerSyntax(*intPtrIndex,
"mulFactor unavailable",
strInfix);
chrNext = strInfix[*intPtrIndex];
if (chrNext >= 'a' && chrNext <= 'z')
{
(*intPtrIndex)++;
return stringAppendChar(strPolish,
chrNext,
intMaxPolishLength,
1);
}
intIndexStart = *intPtrIndex;
intSpaceBefore = -1;
while(*intPtrIndex <= intEnd
&&
(chrNext = strInfix[*intPtrIndex]) >= '0'
&&
chrNext <= '9')
{
if (!stringAppendChar(strPolish,
chrNext,
intMaxPolishLength,
intSpaceBefore))
return 0;
intSpaceBefore = 0;
(*intPtrIndex)++;
}
if (*intPtrIndex > intIndexStart)
return -1;
if (chrNext == '(')
{
intLevel = 1;
(*intPtrIndex)++;
intInner = *intPtrIndex;
while (intLevel > 0 && *intPtrIndex <= intEnd)
{
if ((chrNext = strInfix[(*intPtrIndex)++]) == '(')
{
intLevel++;
}
else
{
if (chrNext == ')')
{
intLevel--;
}
}
}
if (intLevel != 0)
return errorHandlerSyntax
(*intPtrIndex,
"Unbalanced left parenthesis",
strInfix);
if (!expression(strInfix,
strPolish,
&intInner,
*intPtrIndex - 2,
intMaxPolishLength))
return errorHandlerSyntax
(intInner,
"Expression doesn't appear in parentheses",
strInfix);
return -1;
}
return 0;
}
// ---------------------------------------------------------------
// Convert string to an unsigned integer
//
// int string2UnsignedInt(char *strInstring)
//
//
STRING2UNSIGNEDINT
{
int intIndex1 = 0;
int intValue = 0;
for (; strInstring[intIndex1] != '\0'; intIndex1++)
{
if (strInstring[intIndex1] < '0'
||
strInstring[intIndex1] > '9') break;
intValue = intValue * 10
+
strInstring[intIndex1] - (int)'0';
}
return intValue;
}
// ---------------------------------------------------------------
// Append character to string
//
// int stringAppendChar(char *strInstring,
// char chrNew,
// int intMaxLength,
// int intSpaceBefore)
//
STRINGAPPENDCHAR
{
int intLength = stringLength(strString);
int intSpaceBeforeInEffect =
intSpaceBefore
&&
intLength > 0
&&
strString[intLength - 1] != ' ';
if (intLength
intMaxLength - (intSpaceBeforeInEffect ? 2 : 1))
{
errorHandler
("Cannot append character(s): insufficient storage");
return 0;
}
if (intSpaceBeforeInEffect)
{
strString[intLength++] = ' ';
}
strString[intLength] = chrNew;
strString[intLength + 1] = '\0';
return -1;
}
// ---------------------------------------------------------------
// Return string length
//
// int stringLength(char *strInstring)
//
STRINGLENGTH
{
int intIndex1;
for (intIndex1 = 0;
strInstring[intIndex1] != '\0';
intIndex1++) { }
return intIndex1;
}
// ---------------------------------------------------------------
// Test case
//
// void testCase(char *strInfix, char *strExpected, int intMalloc)
//
TESTCASE
{
char *strPolish;
int intMaxPolishLength = 0;
int intReq = intMalloc > 0
?
intMalloc
:
MAX((intMaxPolishLength
=
stringLength(strInfix) << 1)
+
1,
10);
printf("\n\nConverting \"%s\": expect \"%s\"",
strInfix,
strExpected);
strPolish = (char *)malloc(intReq);
if (strPolish == 0)
errorHandler("Can't get storage");
printf("\n\"%s\"\n",
(infix2Polish(strInfix,
strPolish,
intMaxPolishLength)
?
strPolish
:
"Conversion failed"));
free(strPolish); // cf. Schildt, C: the Complete Reference
}
// ---------------------------------------------------------------
// Tester
//
// void tester()
//
TESTER
{
testCase("1", "1", intMalloc);
testCase("1+1", "1 1 +", intMalloc);
testCase("(10+613)*a", "10 613 + a *", intMalloc);
testCase(")", "Error", intMalloc);
testCase("1)", "Error", intMalloc);
testCase("(((1))))", "Error", intMalloc);
testCase("10 113 + a *", "Error", intMalloc);
testCase("(10 + 113) * a", "10 113 + a *", intMalloc);
testCase(" ( 10 + 113 ) * a ", "10 113 + a *", intMalloc);
testCase("(", "Error", intMalloc);
testCase("((((2", "Error", intMalloc);
testCase("////2", "Error", intMalloc);
testCase("", "Error", intMalloc);
testCase("()", "Error", intMalloc);
testCase("(((5))", "Error", intMalloc);
testCase("(((5)))", "5", intMalloc);
testCase("((5))", "5", intMalloc);
testCase("5", "5", intMalloc);
testCase("((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a", "10 113 2 2
4 3 + / + 2 + 2 + - + a *", intMalloc);
testCase("a", "a", intMalloc);
testCase(" a + b ", "a b +", intMalloc);
testCase(" a + b ", "Malloc bound failure", 5);
}