Convert expressions that are in infix notation to postfix notation. The expressi
ID: 3870141 • Letter: C
Question
Convert expressions that are in infix notation to postfix notation. The expressions might contain parentheses and these operators: =, ONLY, NEVER, AND, OR.
int convertToPostfix(char *pszInfix, Out out)
It returns 0 if it converted successfully. Otherwise, it returns a value which indicates an error in the infix expression (e.g., missing left paren, missing right paren).
It populates the out array using the addPostfixOut function (provided in the driver).
For modularity, you will need to divide convertToPostfix into multiple functions.
The program reads in an input file:
The next step the driver scans it in an stores it in a buffer
in driver:
At this point it calls convertToPostFix to convert it to
RECIT N =
RECIT Y =
PROF CLARK =
PROF CLARK NEVER
PROF CLARK ONLY
PROF CLARK NEVER DEPT CS = AND
RECIT Y = PROF CLARK = PROF GIBSON = OR AND
/******************************************************************************
cs2123p1Driver.c by Larry Clark
Purpose:
This program reads infix expressions and converts them from infix to postfix
using a stack.
Command Parameters:
n/a
Input:
The standard input file stream contains infix expressions (one per input text line).
Tokens in the expressions will be separated by one space.
Some sample data:
1. RECIT = N
2. RECIT = Y
3. PROF = CLARK
4. PROF NEVER CLARK
5. PROF ONLY CLARK
6. PROF = CLARK AND RECIT = N
7. PROF NEVER CLARK AND DEPT = CS
8. RECIT = Y AND ( PROF = CLARK OR PROF = GIBSON )
9. LANG ONLY C
10. ( LANG ONLY C OR LANG ONLY JAVA ) AND PREREQ NEVER CS2123
11. DEPT = CS AND RECIT = Y AND LANG = JAVA
12. DEPT = CS AND ( RECIT = Y OR LANG = PYTHON ) AND PROF = CLARK
13. DEPT = CS AND RECIT = Y OR LANG = PYTHON AND PROF = CLARK
Results:
For each expression, print the original expression and its
corresponding postfix expression.
Returns:
0 - normal
901 - stack usage error (e.g., popping an empty stack)
902 - PostfixOut overflow
903 - algorithm error (see message for details)
Notes:
1. This program uses an array to implement the stack. It has a maximum of
MAX_STACK_ELEM elements.
2. This program uses an PostfixOut array for the resulting postfix expression.
It has a maximum of MAX_OUT_ITEM elements.
*******************************************************************************/
// If compiling using visual studio, tell the compiler not to give its warnings
// about the safety of scanf and printf
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
#include "cs2123p1.h"
#include "avb984p1.c"
// The following structure is used by the categorize function to help
// categorize tokens and provide the precedence.
static struct
{
char szSymbol[MAX_TOKEN + 1]; // token symbol such as "("
int iCategory; // CAT_OPERATOR, CAT_OPERAND, CAT_LPAREN or CAT_RPAREN
int iPrecedence; // 0 - lowest precedence, 3 - highest precedence
} symbolDefM[] =
{
{"(", CAT_LPAREN, 0}
, {")", CAT_RPAREN, 0}
, {"=", CAT_OPERATOR, 2}
, {"NEVER", CAT_OPERATOR, 2}
, {"ONLY", CAT_OPERATOR, 2}
, {"AND", CAT_OPERATOR, 1}
, {"OR", CAT_OPERATOR, 1}
, {"", 0, 0}
};
// Stack implementation using arrays. You are not required to document these.
void push(Stack stack, Element value)
{
if (stack->iCount >= MAX_STACK_ELEM)
ErrExit(ERR_STACK_USAGE
, "Attempt to PUSH more than %d values on the array stack"
, MAX_STACK_ELEM);
stack->stackElementM[stack->iCount] = value;
stack->iCount++;
}
Element pop(Stack stack)
{
if (isEmpty(stack))
ErrExit(ERR_STACK_USAGE
, "Attempt to POP an empty array stack");
stack->iCount--;
return stack->stackElementM[stack->iCount];
}
Element topElement(Stack stack)
{
if (isEmpty(stack))
ErrExit(ERR_STACK_USAGE
, "Attempt to examine topElement of an empty array stack");
return stack->stackElementM[stack->iCount-1]; // return the top
}
int isEmpty(Stack stack)
{
return stack->iCount <= 0;
}
Stack newStack()
{
Stack stack = (Stack) malloc(sizeof(StackImp));
stack->iCount = 0;
return stack;
}
void freeStack(Stack stack)
{
free (stack);
}
// Main program for the driver
int main(int argc, char *argv[])
{
// Allocate the memory for the postfix result
PostfixOut postfixOut = malloc(sizeof(PostfixOutImp));
char szInputBuffer[100]; // entire input line
int rc;
int iLineCount = 0;
// read text lines containing expressions until EOF
while (fgets(szInputBuffer, 100, stdin) != NULL)
{
iLineCount++;
// Ignore the line if it only contains a linefeed
if (szInputBuffer[0] == ' ')
continue;
printf("Expr # %d: %s", iLineCount, szInputBuffer);
postfixOut->iPostfixOutCount = 0; // reset out to empty
// Invoke the student's convertToPostfix function
rc = convertToPostfix(szInputBuffer, postfixOut);
switch (rc)
{
case 0: // ok so print the postfix
printPostfixOut(postfixOut);
break;
case WARN_MISSING_LPAREN:
printf(" Warning: missing left parenthesis ");
break;
case WARN_MISSING_RPAREN:
printf(" Warning: missing right parenthesis ");
break;
case WARN_MISSING_OPERATOR:
printf(" Warning: missing operator ");
break;
case WARN_MISSING_OPERAND:
printf(" Warning: missing operand ");
break;
default:
printf(" warning = %d ", rc);
}
}
printf(" ");
free(postfixOut);
fclose(stdin);
fclose(stdout);
return 0;
}
/******************** addPostfixOut **************************************
void addPostfixOut(PostfixOut postfixOut, Element element)
Purpose:
Adds an element to postfixOut.
Parameters:
I/O PostfixOut postfixOut Stores the postfix expression
I Element element Element structure to be added to postfixOut.
Returns:
n/a
Notes:
- Since postfixOut uses an array, addPostfixOut does a boundary
check for overflow.
**************************************************************************/
void addPostfixOut(PostfixOut postfixOut, Element element)
{
if (postfixOut->iPostfixOutCount >= MAX_OUT_ITEM)
ErrExit(ERR_OUT_OVERFLOW
, "Overflow in the postfixOut array");
postfixOut->postfixOutM[postfixOut->iPostfixOutCount] = element;
postfixOut->iPostfixOutCount++;
}
/******************** printPostfixOut **************************************
void printPostfixOut(PostfixOut postfixOut)
Purpose:
prints the contents of the postfixOutM array to stdout
Parameters:
I PostfixOut postfixOut The postfx expression
Returns:
n/a
Notes:
- Prints 18 tokens from postfixOut per line
**************************************************************************/
void printPostfixOut(PostfixOut postfixOut)
{
int i;
if (postfixOut == NULL)
{
printf("*** ERROR PostfixOut is NULL ");
return;
}
printf(" ");
// loop through each element in the postfixOut array
for (i = 0; i < postfixOut->iPostfixOutCount; i++)
{
printf("%s ", postfixOut->postfixOutM[i].szToken);
if ((i + 1) % 18 == 0)
printf(" ");
}
printf(" ");
}
/******************** categorize **************************************
void categorize(Element *pElement)
Purpose:
Categorizes a token providing its precedence (0 is lowest, higher
integers are a higher precedence) and category (operator, operand,
left paren, right paren).
Since the category is an integer, it can be used in a switch statement.
Parameters:
I/O Element *pElement pointer to an element structure which
will be modified by this function
Returns:
n/a
Notes:
- The input parameter, pElement must point to an existing Element
structure. Its attribute, szToken, must already be populated.
- This function will populate the iCategory and
iPrecedence values in the Element structure referenced by pElement.
- Uses the symbolDefM array to help categorize tokens
**************************************************************************/
void categorize(Element *pElement)
{
int i;
// loop through the symbolDefM array until an empty symbol value is found
// marking the end of the symbolDefM array
for (i = 0; symbolDefM[i].szSymbol[0] != ''; i++)
{
// does the element's token match the symbol in the symbolDefM array?
if (strcmp(pElement->szToken, symbolDefM[i].szSymbol) == 0)
{ // matched, so use its precedence and category
pElement->iPrecedence = symbolDefM[i].iPrecedence;
pElement->iCategory = symbolDefM[i].iCategory;
return;
}
}
// must be an operand
pElement->iPrecedence = 0;
pElement->iCategory = CAT_OPERAND;
}
/******************** ErrExit **************************************
void ErrExit(int iexitRC, char szFmt[], ... )
Purpose:
Prints an error message defined by the printf-like szFmt and the
corresponding arguments to that function. The number of
arguments after szFmt varies dependent on the format codes in
szFmt.
It also exits the program with the specified exit return code.
Parameters:
I int iexitRC Exit return code for the program
I char szFmt[] This contains the message to be printed
and format codes (just like printf) for
values that we want to print.
I ... A variable-number of additional arguments
which correspond to what is needed
by the format codes in szFmt.
Returns:
Returns a program exit return code: the value of iexitRC.
Notes:
- Prints "ERROR: " followed by the formatted error message specified
in szFmt.
- Prints the file path and file name of the program having the error.
This is the file that contains this routine.
- Requires including
**************************************************************************/
void ErrExit(int iexitRC, char szFmt[], ... )
{
va_list args; // This is the standard C variable argument list type
va_start(args, szFmt); // This tells the compiler where the variable arguments
// begins. They begin after szFmt.
printf("ERROR: ");
vprintf(szFmt, args); // vprintf receives a printf format string and a
// va_list argument
va_end(args); // let the C environment know we are finished with the
// va_list argument
printf(" Encountered in file %s ", __FILE__); // this 2nd arg is filled in by
// the pre-compiler
exit(iexitRC);
}
/******************** getToken **************************************
char * getToken (char *pszInputTxt, char szToken[], int iTokenSize)
Purpose:
Examines the input text to return the next token. It also
returns the position in the text after that token. This function
does not skip over white space, but it assumes the input uses
spaces to separate tokens.
Parameters:
I char *pszInputTxt input buffer to be parsed
O char szToken[] Returned token.
I int iTokenSize The size of the token variable. This is used
to prevent overwriting memory. The size
should be the memory size minus 1 (for
the zero byte).
Returns:
Functionally:
Pointer to the next character following the delimiter after the token.
NULL - no token found.
szToken parm - the returned token. If not found, it will be an
empty string.
Notes:
- If the token is larger than iTokenSize, we return a truncated value.
- If a token isn't found, szToken is set to an empty string
- This function does not skip over white space occurring prior to the token.
**************************************************************************/
char * getToken(char *pszInputTxt, char szToken[], int iTokenSize)
{
int iDelimPos; // found position of delim
int iCopy; // number of characters to copy
char szDelims[20] = " "; // delimiters
szToken[0] = '';
// check for NULL pointer
if (pszInputTxt == NULL)
ErrExit(ERR_ALGORITHM
, "getToken passed a NULL pointer");
// Check for no token if at zero byte
if (*pszInputTxt == '')
return NULL;
// get the position of the first delim
iDelimPos = strcspn(pszInputTxt, szDelims);
// if the delim position is at the first character, return no token.
if (iDelimPos == 0)
return NULL;
// see if we have more characters than target token, if so, trunc
if (iDelimPos > iTokenSize)
iCopy = iTokenSize; // truncated size
else
iCopy = iDelimPos;
// copy the token into the target token variable
memcpy(szToken, pszInputTxt, iCopy);
szToken[iCopy] = ''; // null terminate
// advance the position
pszInputTxt += iDelimPos;
if (*pszInputTxt == '')
return pszInputTxt;
else
return pszInputTxt + 1;
}
/**********************************************************************
cs2123p1.h
Purpose:
Defines constants:
max constants
error constants
warning constants
categories of tokens (operator, operand, etc.)
boolean constants
Defines typedef for
Token
Element (values placed in stack or out)
StackImp (array stack implementation)
Stack (pointer to a StackImp)
PostfixOutImp (out implementation)
PostfixOut (pointer to an PostfixOutImp)
Notes:
**********************************************************************/
/*** constants ***/
// Maximum constants
#define MAX_STACK_ELEM 20 // Maximum number of elements in the stack array
#define MAX_TOKEN 50 // Maximum number of actual characters for a token
#define MAX_OUT_ITEM 50 // Maximum number of PostfixOut items
// Error constants (program exit values)
#define ERR_STACK_USAGE 901
#define ERR_OUT_OVERFLOW 902
#define ERR_ALGORITHM 903
// Warning constants. Warnings do not cause the program to exit.
#define WARN_MISSING_RPAREN 801
#define WARN_MISSING_LPAREN 802
#define WARN_MISSING_OPERATOR 803
#define WARN_MISSING_OPERAND 804
// categories of tokens
#define CAT_LPAREN 1 // (
#define CAT_RPAREN 2 // )
#define CAT_OPERATOR 3 // Operators are =, NEVER, ONLY /
#define CAT_OPERAND 4 // These are attribute types or values
// boolean constants
#define FALSE 0
#define TRUE 1
/*** typedef ***/
// Token typedef used for operators, operands, and parentheses
typedef char Token[MAX_TOKEN + 1];
// Element typedef used for Element values placed in the stack or out array
typedef struct
{
Token szToken; // Could be a variable, numeric constant, operator,
// left parenthesis or right parenthesis
int iCategory; // A value used to make it easier to handle
// different cases for the types of tokens
int iPrecedence; // An integer representing the operator
// precedence. Higher values imply
// higher precedence.
} Element;
// StackImp typedef defines how we implement a stack using an array
typedef struct
{
int iCount; // number of elements in stack. 0 is empty
Element stackElementM[MAX_STACK_ELEM];
} StackImp;
// Stack typedef defines a pointer to a stack
typedef StackImp *Stack;
// PostfixOutImp typedef defines how we implement out
typedef struct
{
int iPostfixOutCount;
Element postfixOutM[MAX_OUT_ITEM];
} PostfixOutImp;
// PostfixOut typedef defines a pointer to out
typedef PostfixOutImp *PostfixOut;
/********** prototypes ***********/
// Stack functions
void push(Stack stack, Element value);
Element pop(Stack stack);
int isEmpty(Stack stack);
Stack newStack();
void freeStack(Stack stack);
Element topElement(Stack stack);
// Conversion to Postfix functions that Larry provided
void categorize(Element *pElement);
void addPostfixOut(PostfixOut postfixOut, Element element);
void printPostfixOut(PostfixOut postfixOut);
// Conversion to Postfix functions that each student must implement
int convertToPostfix(char *pszInfix, PostfixOut postfixOut);
// Utility routines
void ErrExit(int iexitRC, char szFmt[], ...);
char * getToken(char *pszInputTxt, char szToken[], int iTokenSize);
#include "cs2123p1.h"
#include
#include
#include
#include
#include
**************My Code for the function (avb984p1.c)***********
convertToPostFix(char *pszInfix, PostfixOut out)
{
Stack stack = newStack();
Token szToken; //token string to store in Element variables
while ((pszInfix = getToken(pszInfix, szToken, MAX_TOKEN + 1)) != 0) //while there are tokens in the line of input
{
/***Element set up***/
Element element;
strcpy(element.szToken, szToken); //store the token in the element
categorize(&element); //initialize the Element variable's values based on the token string entered
}
/***Actual conversion***/
switch (element.iCategory)
{
case CAT_OPERAND:
addOut(out, element);
break;
case CAT_OPERATOR:
while(isEmpty(stack) == FALSE && element.iPrecedence < topElement(stack).iPrecedence)
//loop until the stack is empty or there's no more operator in the stack with a lower precedence than the top of the stack
{
addOut(out, pop(stack)); //POP and OUT the higher precedence operator from the stack
}
push(stack, element);
break;
case CAT_LPAREN:
push(stack, element);
break;
case CAT_RPAREN:
while (isEmpty(stack) == FALSE && topElement(stack).iCategory != CAT_LPAREN)
{
addOut(out, pop(stack)); //POP and OUT content of the stack until left parenthesis is found
}
if (isEmpty(stack) == TRUE) //if we didn't find a (
{
freeStack(stack); //at this point we are done using the stack
return WARN_MISSING_LPAREN; //return error
}
pop(stack); //POP and get rid of (
break;
}
/***Remaining Stack***/
while (isEmpty(stack) == FALSE) //goes through the remaining stack until empty
{
if (topElement(stack).iCategory == CAT_LPAREN)//if an unmatched ( is found
{
freeStack(stack); //at this point we are done using the stack
return WARN_MISSING_RPAREN; //return error
}
addOut(out, pop(stack)); //POP and OUT the stack
}
freeStack(stack); //at this point we are done using the stack
return 0; //return success
}
Any help with my code? my function in avb984p1.c comes up with 2 errors on one line which are listed below.
24 29 V:projectsvb984p1.c [Error] 'element' undeclared (first use in this function)
24 29 V:projectsvb984p1.c [Note] each undeclared identifier is reported only once for each function it appears in
RECIT N =
RECIT Y =
PROF CLARK =
PROF CLARK NEVER
PROF CLARK ONLY
PROF CLARK NEVER DEPT CS = AND
RECIT Y = PROF CLARK = PROF GIBSON = OR AND
I1 avb984pl.c e213pDriveres2123pl.h #include #include #include #include #include #include "cs2123p1.h" 2 stdio.h» string.h> stdarg.h> 6 convertToPostFix(char *pszInfx, Postfixut out) 12 13 Stack stack newstack) Token szToken //token string to store in Element variables while ((ps:1nfix getToken(pszInfix, szToken, MAX TOKEN + 1)) != e) //while there are tokens in the line of input Element set up Element elenent strcpy(element.szToken, szToken) //store the token in the element categorize(&element;) /initialize the Element variable 's values based on the token string entered 19 23 "Actual conversion 25 26 27 case CAT OPERAND: addout (out, element) breakj 30 31 case CAT OPERATOR: while(isEmpty( stack)-. FALSE && element, iPrecedencetopElement(stack).iPrecedence) /loop until the stack is empty or there's no more operator in the stack with a Lower precedence than the top of the stack 34 35 36 addout (out, pop (stack)) /POP and OUT the higher precedence operator from the stack push (stack, element)5Explanation / Answer
There is an error in the code - the main while loop that starts on line 16 is ended too early by the closing bracket on line 22. That closing bracket should actually be after line 56 since all the lines in between are part of the process of parsing the token just gotten in that iteration. the "Remaining stack" part is outside the this while loop.
Thus, move thr closing bracket from line 22 to line 57. That should fix it, logic looks fine.