Problem: Write a C program that reads an infix or postfix expression from an inp
ID: 3681903 • Letter: P
Question
Problem: Write a C 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
Grading Rubric
Comments and formatting of code……………..…5
Stack methods……………………………………………40
Appropriate naming of variables ……………….. 5
Correct file I/O………………………………………... 5
Correct evaluation of Postfix……………………….10
Correct Evaluation of Infix…………………………..10
Correct output format…………………………………5
Total ………………………………………………………80
Explanation / Answer
Prefix Expression Evaluation in C :-
-------------------------------------------------------
Prefix.c :-
}
C Program for Evaluation of Postfix Expression :-
-----------------------------------------------------------------------
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 50 int stack[MAX];
char post[MAX];
int top=-1;
void pushstack(int tmp);
void calculator(char c);
void main() { int i; clrscr();
printf("Insert a postfix notation :: ");
gets(post);
for(i=0;i<strlen(post);i++) {
if(post[i]>='0' && post[i]<='9')
{
pushstack(i);
}
if(post[i]=='+' || post[i]=='-' || post[i]=='*' || post[i]=='/' || post[i]=='^')
{
calculator(post[i]);
}
}
printf(" Result :: %d",stack[top]);
getch();
}
void pushstack(int tmp) {
top++;
stack[top]=(int)(post[tmp]-48);
}
void calculator(char c) {
int a,b,ans;
a=stack[top];
stack[top]='';
top--;
b=stack[top];
stack[top]='';
top--;
switch(c) {
case '+':
ans=b+a;
break;
case '-':
ans=b-a;
break;
case '*':
ans=b*a;
break;
case '/':
ans=b/a;
break;
case '^':
ans=b^a;
break;
default: ans=0;
}
top++;
stack[top]=ans;
}
#include<stdio.h> #include <stdlib.h> #include <string.h> #include<math.h> #define STACK_MAX 500 #define OPERAND 10 #define OPERATOR 20 /* stack structure */ typedef struct prexp { int top; int stack[STACK_MAX]; }stck; // Init the stack void init(stck *st ) { st->top=-1; //memset(st->stack, 0, STACK_MAX); } void push(stck *st,int num) { if(st->top == STACK_MAX) { printf("Stack Overflow "); exit(-1); } st->top++; st->stack[st->top]=num; } int pop(stck *st) { int num; if(st->top < 0 ) { printf("Stack Underflow "); exit(-1); } num=st->stack[st->top]; st->top--; return num; } int top(stck *st) { return st->stack[0]; } // evaluate an expression void eval(stck *st,char op,int num1,int num2) { int res; switch(op) { case '+': res=num1+num2; break; case '-': res=num1-num2; break; case '*': res=num1*num2; break; case '/': res=num1/num2; break; case '%': res=num1%num2; break; case '$': res=pow(num1,num2); break; } push(st,res); } int gettype(char c) { switch(c) { case '+': case '-': case '*': case '/': case '$': case '%': return OPERATOR; default : return OPERAND; } } int main(int argc, char *argv[]) { if ( argc != 2 ) /* argc should be 2 for correct execution */ { /* argv[0] is the program name */ /* argc is the count of the number of strings in argv */ /* In this case argc=2 as argv[0] contains the filename argv[1] is prefix expression respectively */ printf( "Invalid Syntax :: Format - prefix.exe expr "); return -1; } else { char * pre; int num1,num2,item,l,i; stck stk; init(&stk); pre = argv[1]; l=strlen(pre); for(i=l-1;i>=0;i--) { if(pre[i]==' ' || pre[i]=='') //just in case! continue; switch(gettype(pre[i])) // process type { case OPERAND : item=pre[i]-'0'; // string to int conversion push(&stk,item); break; case OPERATOR : num1=pop(&stk); num2=pop(&stk); eval(&stk,pre[i],num1,num2); break; } } if(stk.top != 0 ) { printf("Invalid Expression! "); return -1; } printf("Result = %d ",top(&stk)); // print result return 0 ; }}
C Program for Evaluation of Postfix Expression :-
-----------------------------------------------------------------------
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 50 int stack[MAX];
char post[MAX];
int top=-1;
void pushstack(int tmp);
void calculator(char c);
void main() { int i; clrscr();
printf("Insert a postfix notation :: ");
gets(post);
for(i=0;i<strlen(post);i++) {
if(post[i]>='0' && post[i]<='9')
{
pushstack(i);
}
if(post[i]=='+' || post[i]=='-' || post[i]=='*' || post[i]=='/' || post[i]=='^')
{
calculator(post[i]);
}
}
printf(" Result :: %d",stack[top]);
getch();
}
void pushstack(int tmp) {
top++;
stack[top]=(int)(post[tmp]-48);
}
void calculator(char c) {
int a,b,ans;
a=stack[top];
stack[top]='';
top--;
b=stack[top];
stack[top]='';
top--;
switch(c) {
case '+':
ans=b+a;
break;
case '-':
ans=b-a;
break;
case '*':
ans=b*a;
break;
case '/':
ans=b/a;
break;
case '^':
ans=b^a;
break;
default: ans=0;
}
top++;
stack[top]=ans;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.