Reverse Polish Notation Calculator

You are to write a program that implements a stack-based Reverse Polish Notation Calculator.

Reverse Polish Notation is a mathematical notation in which every operator follows all of its operands. It is sometimes called postfix notation, and does not require any parentheses as long as each operator has a fixed number of operands.

From Wikipedia:

In reverse Polish notation the operators follow their operands; for instance, to add 3 and 4, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 4 + 5" in conventional notation would be written "3 4 5 +" in RPN: 4 is first subtracted from 3, then 5 added to it.

he algorithm to implement this type of calculator is as follows:

 while there are input tokens left: read the next token if the token is a value: push it onto the stack else ( assume the token is an operator ): it is already known that the operator takes N arguments if there are fewer than N values on the stack: ERROR: The user has not provided enough input values else: pop the top N values from the stack evaluate the operator, with the values as arguments push returned results (if any) back onto the stack end if end if end while if there is only one value on the stack: that value is the result of the mathematical expression else if there are more than one value on the stack: The user input too many values endif 

processing the input

The input will be a single line of space separated characters, numbers and words.

You should scan in a single line of text from the keyboard, using fgets.

Then, use strtok to separate the string, using a single space character " " as the delimiter.

Process each token in the string using code that implements the algorithm shown above

HINT: use strncmp to compare the input against known values of operators, shown in the table above.

The stack

Your program should implement a stack data structure using a linked list, in order to store the values of the expression. You should use two types of struct objects to accomplish this task. They should have the following components:

Node:

value for calculation (double)

reference to previous node on stack (pointer to struct of this same type)

Stack:

reference to top of stack (pointer to node)

size of stack (integer)

Implement the following functions for your stack:

new_node:

This should take in the value to store inside the node. It will allocate memory for the node using malloc, copy the data into the node, and return the pointer to the newly created node.

push:

This function should take two parameters: A pointer to the overall stack structure to modify, and a pointer to the node to push on the stack. It must update the references on the stack and the node itself, to attach the node to the top of the stack, and increment the size counter in the stack.

pop:

This function should take one parameter: A pointer to the overall stack structure to pop a node from. If there are any nodes on the stack, it should remove the node at the top of the stack, decrement the stack size counter, and return the pointer to the node that was previously on the top of the stack. If there are no nodes on the stack, it should returnNULL.

print:

The only parameter to this function is a pointer to the stack. This function should print out the values in the stack, each one on separate lines. It should print one additional newline ' ' after the list is empty.