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;

}