Write a C program that can take infix and postfix expressions to evaluate If the
ID: 3682301 • Letter: W
Question
Write a C program that can take infix and postfix expressions to evaluate
If the expression is an infix expression then the program converts the infix expression to a postfix expression
And then the program evaluates the postfix notation.
C only!
Problem: Write a program that reads an infix or postfix expression from an input file, evaluates the expression and outputs the result.
Objectives: The objective of this assignment is for students to demonstrate a working knowledge of: Stack implementation using a linked list Evaluation of postfix notation Evaluation of infix notation
Requirements:
When your program is run, it should read input from an input file one line at a time. Each line will begin with the number 1 or 2 followed by a space. 1 indicates that the expression which follows, is in infix notation; while 2 indicates that the expression which follows is in post fix notation. Your program should read and process each line of input, outputting the postfix notation and the value that the expression evaluates to. Output should be written to a file called output.txt the output file will consist of all of the calculated output, each written on a new line in the file. Your program should continue to read and process data from the input file, until a line beginning with the number 0 is encountered. The name of your input file will be passed as an argument to main so it should not be hardcoded in your program
Required functions: Your program should include the following functions For the stack implemented as a linked list
1. stack* initStack() : this creates and initializes the values of the stack implemented as a linked list
2. stack* push(stack *s, char c): takes a stack pointer as a parameter and adds the character parameter to the top of the stack and returns a pointer to the updated stack
3. char pop(stack *s): pops the stack and returns the character popped out
4. char peek (stack *s): looks at the top value on the stack and returns the value seen
5. int IsEmpty(stack *s)checks to see if the stack is empty returning 0 for false and 1 for true.
6. void evaluatePostfix(char *) which takes a postfix expression as a char array and an integer indicating the length of the array. The function should: - write the expression to the output file - evaluate the expression using a stack - and write the integer value obtained to the output file as shown in the sample output
7. void evaluateInfix(char *) which takes an infix expression, - converts it to the postfix form - and then evaluates the expression. - Both the postfix notation and the value it evaluates to, are written to the output file (as shown in the sample output).
Note that these are the required functions but you are allowed to create additional helping functions if you wish.
What do you submit? For this assignment you are required to submit your source code as a single .c file called ExpEvaluator.c. All submissions are to be made via Webcourses by the deadline. Email Assignments will not be accepted. There will be NO EXTENSION FOR THIS ASSIGNMENT. You may choose to submit up to 24 hours late, with 15% grade penalty.
Note: If your program does not compile on Eustis you will receive a maximum score of 40 if your code has all of the functions. If your code does not compile and there are missing functions, then you will receive a grade lower than 40.
Expectations for code testing: Your code will be tested on Eustis. The test file used by the TA will not be the one given in the sample input. However, it will match the specifications given in the assignment. For example there may be more or less lines of input but the file format will be the same and the data will end with a 0.
Sample input.txt
1 (5 + 4)
2 3 4 +
1 2 * 2 /(1 + 3)
0
Sample output file from running code
5 4 + = 9
3 4 + = 7
2 2 * 1 3 + / = 1
Sample2 input.txt
2 7 5 - 2 +
1 3 * (5 – 2 )
1 5/1 + 3
0
Sample output2 file from running code
7 5 - 2 + = 4
3 5 2 - * = 9
5 1 / 3 + = 8
Explanation / Answer
input.txt
1 (5 + 4)
2 3 4 +
1 2 * 2 /(1 + 3)
2 7 5 - 2 +
1 3 * (5 – 2 )
1 5/1 + 3
0
main.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
FILE * ofp; //output text file pointer ready to go
typedef struct stackitem{ //the structure for the stack linked list
char achar; //the item on the stack node, could be any digit, an operation, or parenthesis
struct stackitem * next; //pointer to the next node of the linked list
} stacknode; //typedef name
typedef struct stack_main{ //structure for saving the stack as a whole
stacknode * top; //pointer to the top node of the stack
int size; //the number of nodes on the stack
} stack; //typedef name
//required functions
char peek(stack * s){ //function peek, to show what char value is on top of the stack
return s->top->achar; //returns the value of the top of stack
}
int IsEmpty(stack * s){ //function to quickly check if the stack is empty
if (s->top==NULL)
return 1; //if it is, return 1
else
return 0; //if it isn't, return 0
}
char pop (stack * s){ //fucntion to remove the node top of the linked list stack
stacknode * temp; //temptr
temp = s->top; //point to the top
s->top=s->top->next; //the new top becomes the 2nd node
temp->next=NULL; //the old top now point to null
s->size=s->size-1; //size decreases by 1
return temp->achar; //return the value that was removed
}
stack *push (stack*s, char value){ //function to put a new node onto the stack with a new value
if (value == '0' || value == '1' || value == '2' || value == '3' || value == '4' || value == '5' || value == '6' || value == '7' || value == '8' || value == '9'){ //if the value is a digit
stacknode * temp = (stacknode*)malloc(sizeof(stacknode)); //make a new node
if (temp!= NULL){ //node creation was successful, put it on there
temp->achar=value;
temp->next=s->top;
s->size++;
s->top = temp;
}
}
else { //if the value coming in isn't a digit, it is an operation, and the stack must be changed
int numsaver; //for holding the first digit value
int numsaver2; //for holding the second digit value
int holdans; //for holding the answer to the operation
char backtochar; //turn the answer back to a char
if (value=='+'){ //if the operation is +
numsaver = s->top->next->achar - '0' ; //turn to int
numsaver2= s->top->achar - '0' ; //turn to int
holdans = numsaver + numsaver2; //add the 2 together
backtochar = (holdans + '0'); //turn it back to char
s->top->next->achar = backtochar;
pop(s); //pop the top
}
if (value=='-'){ //if the operation is -
numsaver = s->top->next->achar - '0' ; //turn to int
numsaver2= s->top->achar - '0' ; //turn to int
holdans = numsaver - numsaver2; //subtract the 2 numbers
backtochar = (holdans + '0'); //back to char
s->top->next->achar = backtochar; //add value
pop(s); //pop the top
}
if (value=='*'){ //if the operation is *
numsaver = s->top->next->achar - '0' ; //turn to int
numsaver2= s->top->achar - '0' ; //turn to int
holdans = numsaver * numsaver2; //multiply the 2 numbers
backtochar = (holdans + '0'); //back to char
s->top->next->achar = backtochar; //add value
pop(s); //pop the top
}
if (value=='/'){ //if the operation is /
numsaver = s->top->next->achar - '0' ; //turn to int
numsaver2= s->top->achar - '0' ; //turn to int
holdans = numsaver / numsaver2; //divide the 2 numbers
backtochar = (holdans + '0'); //back to char
s->top->next->achar = backtochar; //add value
pop(s); //pop the top
}
}
return s;
}
stack * initStack(char * equation){ //takes an array (of postfix notation) and starts creating a stack out of it
int i; //for counting
int length=0; //to loop however long the size of the array is
stack* mystack = (stack*)(malloc(sizeof(stack))); //create the main stack structure
if(mystack!=NULL){ //successfully created
mystack->top=NULL; //set the top to null
mystack->size=0; //set the size to 0
}
for(i=0;equation[i+1]!='';i++) //loop until the end is found
length=length+1; //increment length by 1
for(i=0;i<length;i++){ //add values to stack as linked list nodes
push(mystack,equation[i]); //push the value at index i onto the stack, if its a digit it will go on there, if its an operator it will do math
}
return mystack; //return the created stack
}
void evaluatePostfix(char * equation){ //if the equation is in post fix form, it can be easily evaluated
stack * stack_main; //main stack structure
stack_main = initStack(equation); //main stack structure was created, returned from initStack
int i; //for looping
int length=0; //for finding the length of the postfix equation
for (i=0;equation[i+1]!='';i++) //until i hits null
length++; //increment length by 1
for (i=0;i < length;i++){ // for the length of the equation array
fprintf(ofp, "%c ", equation[i]); //print out each character to output.txt
if (i==length-1) //once we get to the end
fprintf(ofp,"= %c ", stack_main->top->achar); //print the answer of the equation on the right side of the equal sign
}
if (IsEmpty(stack_main)==0) //if there is something left on the stack
pop(stack_main); //evaluation over, remove the last single node from the stack
}
void evaluateInfix(char *equation){ //if the equation coming directly from the input file is not in postfix notation, we must first turn it from infix to postfix, then evaluate it. This function does exactly that.
stack* opprStack = (stack*)(malloc(sizeof(stack))); //call memory for the stack that will hold operators instead of numbers
if(opprStack!=NULL){ //was created successfully
opprStack->top=NULL; //set top to null
opprStack->size=0; //0 nodes so far
}
char newchar; //variable to hold the new char coming into the stack
int i; //for indexing
int maxxnodes=0; //max number of operations or digits that will potentially be appearing
int currentindex=0; //the current index of our new post fix array trying to be made
int size1=0; //the size of the infix array
for (i=0;equation[i+1]!='';i++) //calculate the size of the infix array
size1++;
char postfixArray[size1]; //create the new postfix array to add chars to. It will never exceed the size of the original infix array
for(i=0;i<size1;i++){ //need to loop for each char in the infix array
newchar = equation[i]; //newchar grabs a char to evaluate until it gets to null
if(newchar =='0'||newchar=='1'||newchar=='2'||newchar=='3'||newchar=='4'||newchar=='5'||newchar=='6'||newchar=='7'||newchar=='8'||newchar=='9'){ //if the char is a number
postfixArray[currentindex]=newchar; //put it on the postfix array
currentindex++; //move along the index
}
else{ //char was not a number, this means it is either () or + - * /
if(newchar!=')' && newchar != '('){ //not ()
int ifchecker=0; //to make sure things aren't added twice
if (IsEmpty(opprStack)==1){ //case where stack is empty. Anything can come on
stacknode * temp = (stacknode*)malloc(sizeof(stacknode)); //make memory for the node
temp->achar=newchar; //set value of node to the char
temp->next=NULL; //next is null
opprStack->size++; //increase size by 1
opprStack->top = temp; //this node is now the top
ifchecker=1; //making sure this char isnt added again
}
if ( (newchar== '+' || newchar == '-') && (peek(opprStack)=='+' || peek(opprStack)=='-') && ifchecker!=1 ) { //the newchar is + or -, and is trying to come in on a + or -
stacknode * temp = (stacknode*)malloc(sizeof(stacknode)); //make memory for the node
temp->achar=newchar; //set value of node to the char
temp->next=opprStack->top; //old top is new node's next
opprStack->size++; //increase size by 1
opprStack->top = temp; //the new top
}
if ( (newchar== '*' || newchar == '/') && (peek(opprStack)=='*' || peek(opprStack)=='/') && ifchecker!=1 ) { //the newchar is * or /, and is trying to come in on a * or /
//we need to throw everything on the stack into the array now, up to a ( or until it is empty
while ( IsEmpty(opprStack) == 0 && peek(opprStack)!='(' ) { //while the stack isnt empty and we dont reach a (
if (peek(opprStack)!='('){ //if we arent at the (, incase there is one
postfixArray[currentindex]=pop(opprStack); //pop the top of the stack onto the array
currentindex++; //increment the index
}
}
stacknode * temp = (stacknode*)malloc(sizeof(stacknode)); //same old stack node creation
temp->achar=newchar;
temp->next=opprStack->top;
opprStack->size++;
opprStack->top = temp;
}
if ( (newchar== '+' || newchar == '-') && (peek(opprStack)=='*' || peek(opprStack)=='/') ){ //where a + or - is coming, but the top is * or /
//we need to throw everything on the stack into the array now, up to a ( or until it is empty
while ( IsEmpty(opprStack) == 0 && peek(opprStack)!='(' ) { //while the stack isnt empty and we dont reach a (
if (peek(opprStack)!='('){ //if we arent at the (, incase there is one
postfixArray[currentindex]=pop(opprStack); //pop the top of the stack onto the array
currentindex++; //increment the index
}
}
stacknode * temp = (stacknode*)malloc(sizeof(stacknode)); //same old stack node creation
temp->achar=newchar;
temp->next=opprStack->top;
opprStack->size++;
opprStack->top = temp;
}
if ( (newchar== '+' || newchar == '-') && (peek(opprStack)=='(') && IsEmpty(opprStack) == 0 ) { //stack isnt empty, and a + or - is coming in on a (
stacknode * temp = (stacknode*)malloc(sizeof(stacknode)); //same old stack node creation
temp->achar=newchar;
temp->next=opprStack->top;
opprStack->size++;
opprStack->top = temp;
}
if ( (newchar== '*' || newchar == '/') && (peek(opprStack)=='+' || peek(opprStack)=='-' || peek(opprStack) == '(') && IsEmpty(opprStack) == 0 ){ //stack isnt empty, and a * or / is coming in on an +, -, or (
stacknode * temp = (stacknode*)malloc(sizeof(stacknode));
temp->achar=newchar;
temp->next=opprStack->top;
opprStack->size++;
opprStack->top = temp;
}
}
else { //there is a (
if (newchar == '('){ //add the ( to the stack
stacknode * temp = (stacknode*)malloc(sizeof(stacknode)); //create the node for it, onto the stack it goes
temp->achar=newchar;
temp->next=opprStack->top;
opprStack->size++;
opprStack->top = temp;
}
if (newchar == ')'){ //if we reach a )...
while (peek(opprStack)!='('){ //until we reach a (..
postfixArray[currentindex] = pop(opprStack); //throw everything onto the stack
currentindex++; //increment the index by 1
}
pop(opprStack); // get rid of the (
}
}
}
}
maxxnodes=opprStack->size; //hold the size of the stack
for (i=0;i<maxxnodes;i++){
postfixArray[currentindex]=pop(opprStack); //pop the rest of it onto the array
currentindex++;
}
opprStack->size=0; //now the size is 0, the stack is empty
postfixArray[currentindex]=' '; //clean up the end of the array...
postfixArray[currentindex+1]=''; //add a null char to the end of the array
evaluatePostfix(postfixArray); //now that the array is postfix notation, it can be evaluated by calling evaluatePostfix
}
int main(int argc, char*argv[]) //input file name gets passed to main in the command prompt
{
FILE *ifp; //input file pointer
ifp=fopen(argv[1],"r"); //open the input file to be read
if (ifp==NULL){ //if that open failed...
printf(" Error opening file... Aborting "); //Something went wrong trying to pass the name, cancel program
return 0;
}
//input file open successful
ofp = fopen ("output.txt", "w"); //create the output text file to be written to
int inorpost=3; //this variable is for determining if the incoming equation is infix or postfix, for now it is set to 3 for nothing yet
while (inorpost!=0){ //when inorpost becomes 0, the program will stop looping and end
fscanf(ifp,"%d",&inorpost); //scan in inorpost, will either be a 1 or 0
if (inorpost!=0){ //inorpost is not 0, there is an equation to solve
char equation[99]; //variable to hold the whole equation as an array
fgets (equation,99,ifp); //scan in the equation as an array
//this part is for getting rid of any white space in the equation
char *head = equation; //point to the head
char *temptr = head; //temptr pointing to head
while (*head != 0) //while there are still chars left to check
{
if (*head != ' ') //if the head doesn't equal whitespace,let it stay in the array
{
*temptr = *head; //set temptr to head
temptr+= 1; //move temptr over one
}
head += 1;//move head over one
}
*temptr = 0;//set the last char to null
//now that the whitespace is gone, the equation can be passed
if (inorpost==1){ //the equation is infix notation
evaluateInfix(equation); //evaluate this infix equation
}
if (inorpost == 2){ //the equation is postfix notation
evaluatePostfix(equation); //evaluate this postfix equation
}
}
}
fclose(ifp); //close the input file
return 0;//return 0, program is over
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.