Question
Language C Since there are a couple tricky parts about reading and parsing an RPN expressions, you will be given code that will prompt the
Language C
Since there are a couple tricky parts about reading and parsing an RPN expressions, you will be given code that will prompt the user, and parse the expression into a linked list. You will be responsible for writing code to process the linked list which will evaluate the expression. You will also be given code to manipulate a linked list.
Your program needs to handle the same operators that you used in assignment 1, addition (+), subtraction (-), multiplication (*), division (/), and exponentiation (^).
What to submit
A zip file of all of your files, including the starting code.
Example Output
Use input is in bold.
$ ./a.out Please enter an RPN expression: 1 0 / Interpreting input as: (1.00 / 0.00) Error: Requested division by 0 Result: 0.00 $ ./a.out Please enter an RPN expression: 0 0 ^ Interpreting input as: (0.00 ^ 0.00) Error: 0^0 is indeterminate Result: 0.00 $ ./a.out Please enter an RPN expression: 1 1 + Interpreting input as: (1.00 + 1.00) Result: 2.00 $ ./a.out Please enter an RPN expression: 1 1 - Interpreting input as: (1.00 - 1.00) Result: 0.00 $ ./a.out Please enter an RPN expression: 1 2 * Interpreting input as: (1.00 * 2.00) Result: 2.00 $ ./a.out Please enter an RPN expression: 1 2 / Interpreting input as: (1.00 / 2.00) Result: 0.50 $ ./a.out Please enter an RPN expression: 2 3 ^ Interpreting input as: (2.00 ^ 3.00) Result: 8.00 $ ./a.out Please enter an RPN expression: 1 2 3 + * Interpreting input as: (1.00 * (2.00 + 3.00)) Result: 5.00 $
Hints
Make sure to look at the provided header file RPN_linked_list.h. It includes a definition of a RPN_Node struct, and several functions to manipulate a linked list.
To push a number onto a linked list, use the function push. It can be used like:
push(&stack, value);
To pop a number off a linked list, use the function pop. It can be used like:
double value = pop(&stack);
The function prompt_and_parse() will correctly validate an RPN expression, so you do not need to worry about handling input that is invalid. You only need to error check situations like division by 0 and 0^0.
The functions push and pop will correctly manage memory for you, however you still need to free memory for any linked list you use or create. An example of how to properly free the memory is in the starting code, in particularly it correctly frees the linked list named head in the main function.
To help you understand what is in a linked list at any time, use the provided print function. It can be used like:
print_list(head);
It is recommended you put some of these into your program while working so you can understand how the linked lists is structured.
There is a provided function print_as_infix which will take in a linked list in the format that prompt_and_parse gives you. This will print out the expression in the more familiar infix notation so that you can verify your calculator works correctly. The starting code calls this function.
Don't forget that when using multiple files, all .c files must be included on the command line. For example, you should use
clang -Wall file1.c file2.c
or
gcc -Wall file1.c file2.c
depending on the operating system you are using.
Starting Code
In addition to the below code, you will want two files: RPN_linked_list.h and RPN_linked_list.c. Put them into the same directory as your assignment code. You should not modify either of those files.
#include#include #include #include "RPN_linked_list.h" double evaluate_rpn_expression(RPN_Node *head); int main() { RPN_Node *head = prompt_and_parse(); printf("Interpreting input as: "); print_as_infix(head); double result = evaluate_rpn_expression(head); printf("Result: %.2lf ", result); free_list(head); head = NULL; return 0; } double evaluate_rpn_expression(RPN_Node *head) { // This function should walk through the linked list specified by head. // It should also declare another linked list, named stack. // // For each term in the input list, it should check if it is a value or // an operator. If it is a value, it should push it on the stack. // If it is an operator, it should pop two terms off the stack and // use those as the operands to the operator. Be careful of the order of // the terms since for some operators that matters. // // After processing the list, the stack will have one element, which is // the answer. Store it in a double, free the stack and return the answer. return 0; }
RPN_linked_list.h
#ifndef RPN_LINKED_LIST_H
#define RPN_LINKED_LIST_H
#include
typedef struct RPN_Node_struct {
bool is_operator;
char operator;
double value;
struct RPN_Node_struct *next;
} RPN_Node;
// Basic linked list operations
double pop(RPN_Node **head);
void push(RPN_Node **head, double value);
void print_list(RPN_Node *head);
void print_node(RPN_Node *node);
void free_list(RPN_Node *head);
// RPN Specific operations
bool is_operator(char c);
RPN_Node * prompt_and_parse(void);
void print_as_infix(RPN_Node *head);
#endif
RPN_linked_list.c
#include
#include
#include
#include "RPN_linked_list.h"
double pop(RPN_Node **head) {
// Ensure we can pop
if (*head == NULL) {
printf("Error: Attempted to pop NULL pointer ");
return 0;
}
// Store head so we can free it
RPN_Node *temp = *head;
// Store the result so we can return it
double result = (*head)->value;
// Advance the head pointer
* head = (*head)->next;
// Free the old head pointer
free(temp);
return result;
}
void push(RPN_Node **head, double value) {
// Create a new node and fill it in
RPN_Node *temp = malloc(sizeof(RPN_Node));
temp->is_operator = false;
temp->value = value;
temp->next = *head;
// Make the new node the head
* head = temp;
}
void print_list(RPN_Node *head) {
while (head != NULL) {
print_node(head);
head = head->next;
}
}
void print_node(RPN_Node *node) {
if (node->is_operator) {
printf("op: %c ", node->operator);
} else {
printf("val: %lf ", node->value);
}
}
void free_list(RPN_Node *head) {
while (head != NULL) {
// Save pointer to next thing to free
RPN_Node *next = head->next;
// Free up head
head->next = NULL;
free(head);
// Advance head pointer
head = next;
}
}
bool is_operator(char c) {
switch (c) {
case '+':
case '-':
case '*':
case '/':
case '^':
return true;
default:
return false;
}
}
RPN_Node * prompt_and_parse(void) {
printf("Please enter an RPN expression: ");
char buffer[101];
// Reads up to 100 characters from stdin
fgets(buffer, 101, stdin);
// Remove any newlines
char *term = strpbrk(buffer, " ");
if (term) {
* term = '\0';
}
// Setup linked list. We will be adding to the tail
// So we need both head and tail pointers
RPN_Node *head = NULL;
RPN_Node *tail = NULL;;
// Tokenizes buffer by splitting on spaces
char *token = strtok(buffer, " ");
// Count operators/values to validate the RPN expression
int operator_count = 0;
int value_count = 0;
while (token) {
// Declare the next node
RPN_Node *node = malloc(sizeof(RPN_Node));
node->next = NULL;
// Determine the type
if (strlen(token) == 1 && is_operator(token[0])) {
// Operator
node->is_operator = true;
node->operator = token[0];
++operator_count;
// First two terms must be values
if (value_count
// Set counts to impossible values so we will clean up the memory
operator_count = -1;
value_count = -1;
// Stop processing terms
break;
}
} else {
// Treat as a number
node->is_operator = false;
node->value = strtod(token, NULL);
++value_count;
}
// Add node to the list
if (head == NULL) {
// First node in list
head = node;
tail = node;
} else {
// Add after existing tail
tail->next = node;
tail = node;
}
// Move to the next token
token = strtok(NULL, " ");
}
// For a valid RPN (with only binary operators) the following must be
true
// * If only one number, no operators
// * If more than one value, first two terms must be values
// * If two or more values, the number of values must be one more than
the the
// number of operators
// The verification of the first 2 terms is handled above
if (operator_count + 1 != value_count || (value_count == 1 &&
operator_count != 0)) {
// Print an error
printf("Malformed RPN expression. ");
if (operator_count == -1) {
printf("First two terms must be numbers. ");
} else if (value_count == 1 && operator_count != 0) {
printf("With only one number, no operators are allowed. ");
} else {
printf("Must have exactly one more number than operator. Currently
there "
"are %d numbers and %d operators ",
value_count, operator_count);
printf("First two terms must be numbers. ");
}
// Cleanup our memory
free_list(head);
head = NULL;
}
return head;
}
typedef struct RPN_Print_Struct {
char *content;
struct RPN_Print_Struct *next;
} RPN_Print;
void push_print(RPN_Print **head, char *str);
void pop_print(RPN_Print **head);
void print_as_infix(RPN_Node *head) {
RPN_Node *current = head;
RPN_Print *out = NULL;
const size_t buffer_sz = 100;
char buffer[buffer_sz];
while (current != NULL) {
if (current->is_operator) {
// Have an operator
char *rhs = out->content;
pop_print(&out);
char *lhs = out->content;
pop_print(&out);
// Build string
snprintf(buffer, buffer_sz, "(%s %c %s)", lhs, current->operator,
rhs);
char *term = malloc(strlen(buffer) + 1);
strcpy(term, buffer);
push_print(&out, term);
// Cleanup
free(rhs);
rhs = NULL;
free(lhs);
lhs = NULL;
} else {
// Have a value
// Build string
snprintf(buffer, buffer_sz, "%.2lf", current->value);
char *term = malloc(strlen(buffer) + 1);
strcpy(term, buffer);
push_print(&out, term);
}
// Advance to next term
current = current->next;
}
// Done building, just print and cleanup
if (out != NULL) {
printf("%s ", out->content);
free(out->content);
out->content = NULL;
free(out);
}
}
void pop_print(RPN_Print **head) {
RPN_Print *temp = *head;
* head = (*head)->next;
free(temp);
}
void push_print(RPN_Print **head, char *str) {
RPN_Print *temp = malloc(sizeof(RPN_Print));
temp->next = *head;
temp->content = str;
* head = temp;
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started