Reverse Polish Notation Calculator You are to write a program that implements a

Question

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:

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.

Explanation / Answer

Program: please follow these program as shown in below

#include<stdio.h>
#include<conio.h>
#include<ctype.h> char stack[30],str[30]; int tos=0;
void push(char c)
{
if(tos>=29)
{
printf(“stack is full ”); return;
}
else stack[tos++]=c;
}
char pop()
{
tos– –; if(tos<0)
{
printf(“stack is empty ”); return 0;
}
else
return(stack[tos]);
}
main()
{
int i,check_stack=0; char x;
clrscr();
printf(“enter the prefix expression ”); gets(str);
for(i=0;str[i]!=’’;i++)
{
if(!isalpha(str[i]))
{
if(check_stack>1)
printf(“%c”,pop());
push(str[i]);
check_stack=0;
}
else
{
printf(“%c”,str[i]);
check_stack++;
if(check_stack==2)
{
printf(“%c”,pop());
check_stack=0;
}
}
}
while(tos!=0)
printf(“%c”,pop());
getch();
}

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.