C Programming Objectives Practice implementing algorithms based on pseudocode Pr

Question

C Programming

Objectives

Practice implementing algorithms based on pseudocode

Practice parsing text input

Practice managing complex data structures (stack)

Practice using malloc and free

Overview

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. For example, this mathematical notation adds the numbers 5 and 6 together:

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.

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

You are to implement a RPN calculator that supports the following operands:

Your program should take in a single line of text from the keyboard, process the RPN expression, and print out the result of the expression.

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.

Example Execution

NOTE: Call your print function after every token is processed, to show the steps that the program is taking.

Input: 1 2 + 4 * 5 + 3 -

Input: 1.3 7.9 + 2.8 * 3.0 / .75 - sqrt 3 pow

Explanation / Answer

here is the c program for the RPN calculator.

while giving input, give one space in between every character you enter

ex -> 5 3 + 2 -

save the file using appropriate name and run on the windows/linux environement

nameof File.c

gcc nameofFile

----------------------------------------------------------------------------------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h> /* for atof() */
#define MAXOP 100 /* max size of operand or operator */
#define NUMBER '0' /* signal that a number was found */
int getop(char []);
void push(double);
double pop(void);
/* reverse Polish calculator */
main()
{
int type;
double op2;
char s[MAXOP];
while ((type = getop(s)) != EOF) {
switch (type) {
case NUMBER:
push(atof(s));
break;
case '+':
push(pop() + pop());
break;
case '*':
push(pop() * pop());
break;
case '-':
op2 = pop();
push(pop() - op2);
break;
case '/':
op2 = pop();
if (op2 != 0.0)
push(pop() / op2);
else
printf("error: zero divisor ");
break;
case ' ':
printf(" %.8g ", pop());
break;
default:
printf("error: unknown command %s ", s);
break;
}
}
}

#define MAXVAL 100

int sp = 0;
double val[MAXVAL];

void push(double f)
{
if(sp < MAXVAL)
val[sp++]=f;
else
printf("error:stack full, cant push %g ",f);
}

double pop(void)
{
if(sp>0)
return val[--sp];
else
{
printf("error: stack empty ");
return 0.0;
}
}

#include<ctype.h>

int getch(void);
void ungetch(int);

int getop(char s[])
{
int i,c;

while((s[0] = c = getch()) == ' ' || c ==' ')
;
s[1] = '';
  
i = 0;
if(!isdigit(c) && c!='.' && c!='-')
return c;

if(c=='-')
if(isdigit(c=getch()) || c == '.')
s[++i]=c;
else
{
if(c!=EOF)
ungetch(c);
return '-';
}
  
if(isdigit(c))
while(isdigit(s[++i] =c =getch()))
;

if(c=='.')
while(isdigit(s[++i] = c=getch()))
;
  
s[i] = '';
if(c!=EOF)
ungetch(c);
return NUMBER;
}

#define BUFSIZE 100

char buf[BUFSIZE];
int bufp = 0;

int getch(void)
{
return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c)
{
if(bufp >= BUFSIZE)
printf("ungetch: too many characters ");
else
buf[bufp++] = c;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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