Introduction For your first programming assignment, you are to implement a calcu
ID: 3573268 • Letter: I
Question
Introduction
For your first programming assignment, you are to implement a calculator using queues, stacks, and a binary search tree. A queue is used to store an infix expression, which will be read in from a file or from the keyboard. A stack is used to convert the expression on the queue from infix to postfix, with the postfix expression stored in another queue. A second stack is used to convert the postfix expression unitl the stack holds into a single literal. The program generally displays the resulting literal. Since the expression can reference variables, the binary search tree is used to store the values of those variables.
You may use fewer stacks and queues, depending on how you implement your expression processor.
I/O
Your executable must be named calculon. The executable reads in a series of infix expressions, either from a file or from stdin, and will produce, on stdout, the result of the last expression. Here is an example invocation:
where $ is the system prompt. The file to be processed (expr in the example) is a free-format text file. That is, the tokens within are separated by arbitrary amounts of whitespace (i.e. spaces, tabs, and newlines) and every line ends with a newline. If a file name is not given, input is to be read from the keyboard:
The executable must handle the following options:
Here are some example invocations using options:
Here is a program that features some handy-dandy option-handling code that you may use verbatim without credit: options.c
Expressions
Expressions will be composed of literals (integers, real numbers, and quoted strings), variables (tokens beginning with an alphabetic character), and operators ( = + - * / % ^), plus parentheses. All tokens will be surrounded by whitespace. For example, the expression: (x+1)*2; is illegal and should be written as ( x + 1 ) * 2 ;
A token in the input stream can be identified as follows:
a real number will have a . in it
a integer will start with a digit or a minus sign and not have a . in it
a string will start with a double quote and end with a double quote; there may be spaces and tabs within the string
a variable will start with an ASCII letter (upper or lower case) and will be followed by ASCII letters or digits
semicolons and parentheses will appear in tokens by themselves
everything else is an operator
The operators have precedence in increasing order from assignment to plus to minus to times to divides to modulus to exponentiation. Parentheses override precedence. All operators are left associative:
An integer and a real combined together yields a real number:
Two strings added together results in a concatenation of the two operands:
Here is a code snippet for safely concatenating two strings a and b, placing the result in c:
A string combined with a number causes the string to be converted to a number of the same type:
Use atoi or atof to convert a string to an integer or real number, respectively.
Assignment is an operator which changes the value of a variable. The value of an assignment is the value assigned:
Declarations
Variables are declared with the var keyword:
All declarations will appear first. The initializer in a variable declaration will be a number or a string:
Variables and their values should be stored in a binary search tree for later retrieval during the processing of the postfix expression. A variable will only be declared once, so the binary search tree will contain unique keys.
Reading the input
You may find the Art and Science of Programming - C Edition scanner to be useful for this task:
You can read a token with the scanner and then examine the token to see what kind of value it is. You may not use scanf to read into a fixed-length character array.
Error checking
The only error checking you must perform is detecting the use of a variable that was not declared:
After printing the error message, you should exit the program. Other than this one exception, your program will only be tested with valid input.
Implementation details
Use a value structure to hold each element of the expression, where the type field specifies the type of value stored in the structure and the ival, rval, and sval hold an integer, a double, and a string (and variable name), respectively. Here is what the value.h file might look like:
Here is what the value.c file might look like:
All your structures should follow this model. Now, the nodes for your stacks and queues can all references value “objects”. Variables are stored in the binary search tree with the variable name as key and a value object as value.
Your stack must support push and pop in constant time. Your queue must support enqueue and dequeue in constant time.
Explanation / Answer
1. I am writing a C program to evaluate postfix expression. E.g., 6 7 3 * + 5 - = 22 by using stack and queue data structure.Please Follow the below instructions to complete current assignment. Program will accept only sigle digit operand.
a. Assume the following structure definitions for stack and queue and
b. Create the following functions:
Initialize stack
Push stack
Pop stack Initialize queue
Append to queue
Serve from queue
Note: You may include other stack and queue functions if required.
c. You are required to create one stack and one queue (postfix) to store and manipulate the operands and operators in the program.
d. The following algorithm should be used:
1. Read a postfix expression from user input.
2. append each of the character (operand/operator) into postfix queue.
3. While the postfix queue is not empty, serve one character from the postfix queue.
3.1. If the current character is a digit then
3.1.1. Push its integer value on the stack.
3.2. Else if the current character is an operator then
3.2.1. Pop the top element of the stack into variable opd2.
3.2.2. Pop the next element of the stack into variable opd1.
3.2.3. Calculate opd1 operator opd2.
3.2.4. Push the result of the calculation on the stack.
3.3. Pop the top value off the stack. This is the result of evaluating the expression.
001
---------------------------------------------------------Main Program Code--------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#include "queue.h"
int main()
{
Stack myStack;
QUEUE myQueue;
initialize_stack(&myStack);
initialize_queue(&myQueue);
int item;
int opd2;
int opd1;
int total;
printf("Please enter a character ");
scanf("%d",&item);
append(&myQueue,item);
while(queue_empty(&myQueue) != 1)
{
serve(&myQueue);
}//while
if(item = (item % 1 == 0))
{
push(&myStack,item);
}//if
else if(item == operator)
{
opd2 = pop(&myStack);
myStack->top++;
opd1 = pop(&myStack);
myStack->top--;
}//else
}//main
---------------------------------Queue Program:-------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
void initialize_queue(Queue *myQueue)
{
myQueue->count = 0;
myQueue->front = 0;
myQueue->rear = 0;
}
int queue_empty(const Queue *myQueue)
{
if(myQueue->count <= 0){
return 1;
}
else
{
return 0;
}
}
int queue_full(const Queue *myQueue)
{
if(myQueue->count >= MAXQUEUE)
{
return 1;
}
else
{
return 0;
}
}
void append(Queue *myQueue,int item)
{
if(queue_full(myQueue))
{
printf("Queue is full ");
}
else
{
myQueue->rear++;
if(myQueue->rear == MAXQUEUE)
{
myQueue->rear = 0;
}
myQueue->entry[myQueue->rear] = item;
myQueue->count++;
}
}
char serve(Queue *myQueue)
{
int item;
if(queue_empty(myQueue))
{
printf("Queue is empty ");
}
else
{
item = myQueue->entry[myQueue->front];
myQueue->front++;
if(myQueue->front == MAXQUEUE)
{
myQueue->front = 0;
}
myQueue->count--;
}
return item;
}
--------------------------------------------------Queue Header Code--------------------------------------------------
//header declaration
#ifndef QUEUEH
#define QUEUEH
#define MAXQUEUE 50
struct QUEUE
{
int count;
int front;
int rear;
char entry[MAXQUEUE];
};
typedef struct QUEUE Queue;
void initialize_queue(Queue *myQueue);
int queue_empty(const Queue *myQueue);
int queue_full(const Queue *myQueue);
void append(Queue *myQueue,int item);
char serve(Queue *myQueue);
#endif
--------------------------------------------------Stack File --------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
void initialize_stack(Stack *myStack){
myStack->top = -1;
}
int stack_empty(const Stack *myStack){
if(myStack->top < 0){
return 1;
}
else
{
return 0;
}
}
int stack_full(const Stack *myStack)
{
if(myStack->top >= MAXSTACK-1)
{
return 1;
}
else
{
return 0;
}
}
void push(Stack *myStack,int item){
if(stack_full(myStack)){
printf("The stack is full ");
}
else
{
myStack->top++;
myStack->entry[myStack->top] = item;
}
}
char pop(Stack *myStack)
{
int item;
if(stack_empty(myStack))
{
printf("Stack is empty ");
}
else
{
item = myStack->entry[myStack->top];
myStack->top--;
}
return item;
}
--------------------------------------------------Main Program Code--------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#include "queue.h"
int main()
{
Stack myStack;
QUEUE myQueue;
initialize_stack(&myStack);
initialize_queue(&myQueue);
int item;
int opd2;
int opd1;
int total;
printf("Please enter a character ");
scanf("%d",&item);
append(&myQueue,item);
while(queue_empty(&myQueue) != 1)
{
serve(&myQueue);
}//while
if(item = (item % 1 == 0))
{
push(&myStack,item);
}//if
else if(item == operator)
{
opd2 = pop(&myStack);
myStack->top++;
opd1 = pop(&myStack);
myStack->top--;
}//else
}//main
This is my queue program
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
void initialize_queue(Queue *myQueue)
{
myQueue->count = 0;
myQueue->front = 0;
myQueue->rear = 0;
}
int queue_empty(const Queue *myQueue)
{
if(myQueue->count <= 0){
return 1;
}
else
{
return 0;
}
}
int queue_full(const Queue *myQueue)
{
if(myQueue->count >= MAXQUEUE)
{
return 1;
}
else
{
return 0;
}
}
void append(Queue *myQueue,int item)
{
if(queue_full(myQueue))
{
printf("Queue is full ");
}
else
{
myQueue->rear++;
if(myQueue->rear == MAXQUEUE)
{
myQueue->rear = 0;
}
myQueue->entry[myQueue->rear] = item;
myQueue->count++;
}
}
char serve(Queue *myQueue)
{
int item;
if(queue_empty(myQueue))
{
printf("Queue is empty ");
}
else
{
item = myQueue->entry[myQueue->front];
myQueue->front++;
if(myQueue->front == MAXQUEUE)
{
myQueue->front = 0;
}
myQueue->count--;
}
return item;
}
--------------------------------------------------Queue Header code--------------------------------------------------
#ifndef QUEUEH
#define QUEUEH
#define MAXQUEUE 50
struct QUEUE
{
int count;
int front;
int rear;
char entry[MAXQUEUE];
};
typedef struct QUEUE Queue;
void initialize_queue(Queue *myQueue);
int queue_empty(const Queue *myQueue);
int queue_full(const Queue *myQueue);
void append(Queue *myQueue,int item);
char serve(Queue *myQueue);
#endif
--------------------------------------------------Stack Code-----------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
void initialize_stack(Stack *myStack){
myStack->top = -1;
}
int stack_empty(const Stack *myStack){
if(myStack->top < 0){
return 1;
}
else
{
return 0;
}
}
int stack_full(const Stack *myStack)
{
if(myStack->top >= MAXSTACK-1)
{
return 1;
}
else
{
return 0;
}
}
void push(Stack *myStack,int item){
if(stack_full(myStack)){
printf("The stack is full ");
}
else
{
myStack->top++;
myStack->entry[myStack->top] = item;
}
}
char pop(Stack *myStack)
{
int item;
if(stack_empty(myStack))
{
printf("Stack is empty ");
}
else
{
item = myStack->entry[myStack->top];
myStack->top--;
}
return item;
}
--------------------------------------------------Stack Program--------------------------------------------------
#ifndef STACKH
#define STACKH
#define MAXSTACK 50
//global Stack declaration
struct Stack{
int top;
char entry[MAXSTACK];
};
typedef struct Stack stack;
//function declaration
void initialize_stack(Stack *myStack);
int stack_empty(const Stack *myStack);
int stack_full(const Stack *myStack);
void push(Stack *myStack,int item);
char pop(Stack *myStack);
#endif
-------END OF THE CODE----------------------
Do give opportunity to further assist you.
Thanks,
Shweta Sharma - BSR
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.