In C Programming: /*************************************************************

Question

In C Programming:

/******************************************************************************
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:
A = 1 + 2
B = A * 2 + 3
D = A * ( 2 + 3 )
B = 4 / 2
E = A + 4 / B
( ( ( A + B ) ) )
E = ( A + B ) * 5
H = ( ( A + B / 2 ) * 3 + 1 )
Q = ( A * B + ( 3 * 4 + 2 ) * 1 / D )
F = ( A + B ) * ( D / B ) )
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 - Out 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 Out 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 <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <stdlib.h>
#include "cs2123p1.h"

// The following structure is used by the categorize function to help
// categorize tokens and provide the precedence.   
// The iSubcategory won't be used until Program #2.
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
int iSubcategory; // For CAT_OPERAND, this has a value of
// VARIABLE or CONSTANT
} symbolDefM[] =
{
{ "(", CAT_LPAREN, 0, 0 }
, { ")", CAT_RPAREN, 0, 0 }
, { "=", CAT_OPERATOR, 1, 0 }
, { "+", CAT_OPERATOR, 2, 0 }
, { "-", CAT_OPERATOR, 2, 0 }
, { "*", CAT_OPERATOR, 3, 0 }
, { "/", CAT_OPERATOR, 3, 0 }
, { "", 0, 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[])
{
Out out = malloc(sizeof(OutImp)); // for the postfix
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++;
if (szInputBuffer[0] == ' ')
continue;
printf("Expr # %d: %s", iLineCount, szInputBuffer);
out->iOutCount = 0; // reset out to empty

// Invoke the student's convertToPostfix function
rc = convertToPostfix(szInputBuffer, out);
switch (rc)
{
case 0: // ok so print the postfix
printOut(out);
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(out);
fclose(stdin);
fclose(stdout);
return 0;
}

/******************** addOut **************************************
void addOut(Out out, Element element)
Purpose:
Adds an element to out.
Parameters:
I/O Out out Stores the postfix expression
I Element element Element structure to be added to out.
Returns:
n/a
Notes:
- Since out uses an array, addOut does a boundary check for overflow.
**************************************************************************/
void addOut(Out out, Element element)
{
if (out->iOutCount >= MAX_OUT_ITEM)
ErrExit(ERR_OUT_OVERFLOW
, "Overflow in the out array");
out->outM[out->iOutCount] = element;
out->iOutCount++;
}

/******************** printOut **************************************
void printOut(Out out)
Purpose:
prints the contents of the out array to stdout
Parameters:
I Out out The postfx expression
Returns:
n/a
Notes:
- Prints 6 tokens from out per line
**************************************************************************/
void printOut(Out out)
{
int i;
printf(" ");
// loop through each element in the out array
for (i = 0; i < out->iOutCount; i++)
{
printf("%s ", out->outM[i].szToken);
if ((i + 1) % 6 == 0)
printf(" ");
}
printf(" ");
}

/******************** categorize **************************************
void categorize(Element *pElement)
Purpose:
Categorizes a token providing its precedence (0 is lowest, higher
integers are a higher precedence), category (operator, operand,
left paren, right paren) and subcategory (variable, constant).
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, iSubcategory, 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->iSubcategory = 0;
pElement->iCategory = symbolDefM[i].iCategory;
return;
}
}
// must be an operand
pElement->iPrecedence = 0;
pElement->iCategory = CAT_OPERAND;
// If it starts with a number, assume it is a numeric constant
if (pElement->szToken[0] >= '0' && pElement->szToken[0] <= '9')
pElement->iSubcategory = CONSTANT;
else
pElement->iSubcategory = VARIABLE;
}

/******************** 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 <stdarg.h>
**************************************************************************/
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;
}

Here is cs2123p1.h

/**********************************************************************
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)
OutImp (out implementation)
Out (pointer to an OutImp)
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 Out 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 =, +, -, *, /
#define CAT_OPERAND 4 // These are variables or constants

// subcategories of tokens
#define VARIABLE 5
#define CONSTANT 6

// 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 iSubcategory; // If the category is CAT_OPERAND, this
// specifies whether it is a VARIABLE or a CONSTANT.
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;

// OutImp typedef defines how we implement out
typedef struct
{
int iOutCount;
Element outM[MAX_OUT_ITEM];
} OutImp;

// Out typedef defines a pointer to out
typedef OutImp *Out;

/********** 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);
Out newOut();
void addOut(Out out, Element element);
void printOut(Out out);

// Conversion to Postfix functions that each student must implement
int convertToPostfix(char *pszInfix, Out out);

// Utility routines
void ErrExit(int iexitRC, char szFmt[], ...);
char * getToken(char *pszInputTxt, char szToken[], int iTokenSize);

And here is the outline for what I need help with:

/******************************************************************
cs2123p0.c Outline of what to do
Purpose:
This file contains the convertToPostfix function, which is
invoked by the main unctionf in cs2123p1Driver.c to convert
from infix to postfix.

Command Parameters:

Input:
Results:
Return a value indicating if expression was converted successfully.
Populate the using the addout function from s2123p1Driver.c
Returns:
0 if it is converted successfully
1 if there is an error in the infix expression (e.g missing parenthesis)
Notes:

******************************************************************/
#include <stdio.h>
#include <string.h>
#include "cs2123p1.h"

/********************convertToPostfix****************************
int convertToPostfix(char *pszInfix, Out out)

Purpose:

Parameters:

Notes:

Return Value:

******************************************************************/
int convertToPostfix(char *pszInfix, Out out)
{

Stack stack = newStack();
   pszInfix = getToken(pszInputTxt, element.szToken, iTokenSize);

   while (pszInfix != NULL )
   {
       categorize(&pElement);

       switch (element.iCategory)
       {
           case CAT_OPERAND:
               out(element);
               break;

           case CAT_LPAREN:
           push(element);
           break;

           case CAT_OPERATOR:
               operatorPrecedence(stack, out, element);
              
               break;
             
           case CAT_RPAREN:
           if(handleRParen(stack, out, element) == 0)
           return 802; // WARN_MISSING_LPAREN
          
           //no missing L parenthesis
           break;
       }

       pszInfix = getToken(pszInputTxt, element.szToken, iTokenSize);

   }
return 0; //no errors found
  
}
/********************operatorPrecedence****************************
void operatorPrecedence(Stack stack,Out out,element)

Purpose: to check the incoming operator's (IO) precedence against what is on the top of the stack (TOS).
While the stack is not empty, if IO.precedence <= TOS.precedence then out(TOS) otherwise exit function

Parameters:

Notes:

Return Value:
   N/A

******************************************************************/
void operatorPrecedence(Stack stack, Out out, element)
{
          
}

/********************handleRParen****************************
int handleRParen(Stack stack,Out out, element)

Purpose: to keep popping the stack to out until you find a left paren

Parameters:

Notes:

Return Value:
   0 Missing L parenthesis
   1 All matching L parenthesis found

******************************************************************/
int handleRParen(Stack stack,Out out, element)
{

}

CS2123 Program #1 Infix to Postfix (30 points) Note: some Internet browsers won't allow .c and.h files to be downloaded. To avoid that problem, I changed the file name to cs2123p1_h.txt and cs2123p1Driver_c.txt. Please rename them Convert expressions that are in infix notation to postfix notation. The expressions might contain parentheses and these operators: +,-, /,-. In program #2, you will evaluate that postfix expression. The functions getToken and categorize are provided in the cs2123p1Driver.c. These can greatly simplify your code Your code Create your code in cs2123p1.c (not cs2123p1Driver.c). Based on what the driver calls, you need to create (at least) this function: Meaning of the operator xamples int convertToPostfix(char *pszInfix, Out out) · The "-" operator is interpreted as "assign to". "A = 2" means to assign 2 to returns 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 addOut function (provided in the driver). the variable A. · This information is much more important for program #2. Extra Credit (10 pts 100 N) Extra credit is all or nothing. Your program must meet ALL requirements. You will not receive extra credit if your program is turned in late For modularity, you will need to divide convertToPostfix into multiple functions. · N = the number of people who get it completely correct. For example, if To compile the driver (producing cs2123p1Driver.o), use: Precedence rules only 4 people get the extra credit completely correct, they each receive an extra 35 points (10 100 / 4) gcc -g -co cS2123p1Driver.o cs2123p1Driver.c Note that gcc knows to produce a .o file for a .c file when the "-c" switch is specified. You can simply use Evaluate contents in () before others The following errors must be detected: lowe lowe gcc -g -cs2123p1Driver.c gcc -g -co cs2123p1.o cs2123p1.c gcc -g -o p1 cs2123p1Driver.o cs2123p1.o o Missing "(" -- must also be handled for normal credit o Missing ")" -- must also be handled for normal credit o Missing operator To compile your .c file, producing cs2123p1.o: Driver Program and your function in separate files To link your program, producing the executable named p1 issing oper For this program, I provided a driver program which will invoke your function to convert from infix to postfix. Your code must be placed in a You must also turn in your output for the extra credit input file If your program does not follow my programming standards, it will not To execute your program p1 using the standard input file p1lnput.txt Inpu receive extra credit. Why did I provide a driver program? Reduces the amount of code you have to write. This allows you to rror Handline focus on the most important points. Teaches you what it is like to use code written by someone else Shows you the value of programming standards. Provides a design which makes it easier for you to do this program. It End of document Your code must handle errors like the following issing issing o Additional errors are handled for extra credit. is very helpful to have addOut, categorize, and getToken. When an error is encountered, your code for convertToPostfix should return Why must you put your code in a separate file? a non-zero value to the drive am must not terminate s separated i ca mming s for your use please see m ine se revi oa several usefu 4. The output should show a wa oorly form ines ase review this code nthe xtra.txt ine nex ins OC ed memory (e.g obably need to code more than just the

Explanation / Answer

cs2123p1Input.txt

SMOKING = N AND GENDER = F
SMOKING = N AND ( EXERCISE = HIKE OR EXERCISE = BIKE )
GENDER = F AND EXERCISE NOTANY YOGA
SMOKING = N AND EXERCISE = HIKE OR EXERCISE = BIKE
( BOOK = SCIFI )
( ( ( BOOK ONLY SCIFI ) ) )
( ( SMOKING = N )
( ( SMOKING = N ) AND ( BOOK ONLY SCIFI ) AND ( EXERCISE = HIKE ) )
( GENDER = M ) AND EXERCISE = BIKE )

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---