Need convertToPostfix to convert the file from infix to postfix //cs2123p1.c #in
ID: 3783625 • Letter: N
Question
Need convertToPostfix to convert the file from infix to postfix
//cs2123p1.c
#include <string.h>
#include "cs2123p1.h"
/******************** mainConverstion **************************************
int actualConversion(Element element,Out out,Stack stack)
Purpose:
Use switch statments to check for errors and check for precedence to push, pop and out
Parameters:stacks
I Element element Take in the element set up in convertToPostFix.
I Stack stack contains current stack we are using
O Out out Returned output in postfix form if no errors found.
Returns:Converted stack with left parenthesis removed
Functionally:
Integer representing the success of the operation or error found.
0 - no errors and completed.
WARN_MISSING_LPAREN - input is missing a left parenthesis.
WARN_MISSING_RPAREN - input is missing a right parenthesis.
out parm - the converted querry back to convertToPostFix.
Notes:
**************************************************************************/
int mainConversion( PostfixOut out,Stack stack){
Element element;
switch (element.iCategory) //what kind of element is it?
{
case CAT_OPERAND:
addPostfixOut(out, element);
break;
case CAT_OPERATOR:
while (isEmpty(stack) == FALSE && element.iPrecedence < topElement(stack).iPrecedence)
//loop until the stack is empty or no more low prcedence from top
{
addPostfixOut(out, pop(stack)); //pop and out 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) {
addPostfixOut(out, pop(stack)); //pop and out the stack
}
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;
}
return 0;
}
/******************** convertToPostFix **************************************
int convertToPostFix(char *pszInfix, Out out)
Purpose:
Convert a querry line from infix notation to the postfix notation.
Parameters:
I char *pszInfix take in querry to be converted.
O Out out Returned output in postfix form if no errors found.
Returns:
Functionally:
Integer representing the success of the operation or error found.
0 - no errors and completed.
out parm - the converted querry.
Notes:
**************************************************************************/
int restOfStack(Stack stack,PostfixOut out)
{
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
}
addPostfixOut(out, pop(stack)); //pop and out the stack
}
return 0;
}
/******************** convertToPostFix **************************************
int convertToPostFix(char *pszInfix, Out out)
Purpose:
Convert a querry line from infix notation to the postfix notation.
Parameters:
I char *pszInfix take in querry to be converted.
O Out out Returned output in postfix form if no errors found.
Returns:
Functionally:
Integer representing the success of the operation or error found.
0 - no errors and completed.
out parm - the converted querry.
Notes:
**************************************************************************/
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
{
//setting up Elements
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
}
int i;
i=mainConversion(out,stack);
if (i>0) return i;
i=restOfStack(stack,out);
if (i>0) return i;
freeStack(stack); //finished with all of the stack
return 0; //return success
}
/******************************************************************************
cs2123p1Driver.c
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 <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.
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 <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;
}
Explanation / Answer
# include <iostream.h>
# include <string.h>
# include <stdlib.h>
# include <conio.h>
int top=-1;
char Stack[25][100]={NULL};
void push(constchar *);
constchar* pop( );
void postfix_to_infix(constchar *);
int main( )
{
clrscr( );
char Postfix_expression[100]={NULL};
cout<<" Enter the Postfix Expression : ";
cin.getline(Postfix_expression,80);
postfix_to_infix(Postfix_expression);
getch( );
return 0;
}
/*************************************************************************///----------------------------- push(const char) ----------------------///*************************************************************************/void push(constchar *Symbol)
{
if(top==24)
cout<<"Error : Stack is full."<<endl;
else
{
top++;
strcpy(Stack[top],Symbol);
}
}
/*************************************************************************///-------------------------------- pop( ) -----------------------------///*************************************************************************/constchar* pop( )
{
char Symbol[100]={NULL};
if(top==-1)
cout<<"Error : Stack is empty."<<endl;
else
{
strcpy(Symbol,Stack[top]);
strset(Stack[top],NULL);
top--;
}
return Symbol;
}
/*************************************************************************///--------------------- postfix_to_infix(const char *) ----------------///*************************************************************************/void postfix_to_infix(constchar *Postfix)
{
char Infix_expression[100]={NULL};
char Postfix_expression[100]={NULL};
strcpy(Postfix_expression,Postfix);
strcat(Postfix_expression,"=");
int count=0;
char Symbol_scanned[5]={NULL};
do
{
Symbol_scanned[0]=Postfix_expression[count];
if(Symbol_scanned[0]=='/' || Symbol_scanned[0]=='*' ||
Symbol_scanned[0]=='-' || Symbol_scanned[0]=='+' ||
Symbol_scanned[0]=='^' )
{
char Value_1[100]={NULL};
char Value_2[100]={NULL};
char Result[100]={NULL};
strcpy(Value_1,pop( ));
strcpy(Value_2,pop( ));
if(Infix_expression[(count+1)]!='=')
strcpy(Result,"(");
strcat(Result,Value_2);
strcat(Result,Symbol_scanned);
strcat(Result,Value_1);
if(Infix_expression[(count+1)]!='=')
strcat(Result,")");
push(Result);
}
else
push(Symbol_scanned);
count++;
}
while(Postfix_expression[count]!='=');
strset(Infix_expression,NULL);
strcpy(Infix_expression,pop( ));
cout<<" Infix Expression is : "<<Infix_expression;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.