This problem involves writing a calculator that evaluates expressions in Reverse

Question

This problem involves writing a calculator that evaluates expressions in Reverse Polish notation (RPN) (see also here).

Write a C program, in a file rpn.c, that behaves as described below.

Invocation: Your program will be compiled to an executable named rpn (see under Makefile below). It will read its input from stdin and write its output to stdout. Error messages, if any, will be written tostderr.

Input: The input will consist of a sequence of expressions, in RPN, one expression per line.

The syntax of expressions is as follows:

An expression consists of a sequence of tokens separated by blanks and tabs. A token is either a number or one of the binary operators { +, -, *, / }. Each operator takes two operands; an operand may be either an integer constant specified in the input, or the value computed by some other operation.

A number is a sequence of decimal digits. There are no sign characters, i.e., we don't handle negative numbers in the input (however, negative numbers can be simulated by subtracting from 0; for the same reason, negative numbers can arise during computations).

An expression is syntactically correct if there are exactly enough operands to satisfy all the operators in the expression.

To avoid issues arising from floating-point precision problems, all of the arithmetic for this problem (including division) will be done using int values.

Output: The value of each expression evaluated by your program will be written to stdout using the statement

printf("%d ", value)

Program behavior: Your program will read in a line from the input stream, evaluate the expression, and print the result to the output stream. This will be repeated for each line until no more input can be read.

The algorithm for evaluating RPN expressions is as follows:

while there are tokens to be processed do
   tok := next input token;
   if tok is a number n then
      push n on the stack;
   else if tok is an operator op then
      operand2 := pop();
      operand1 := pop();
      val := operand1   op   operand2;
      push val on the stack;
   else
      syntax error;
   endif
endwhile

A brief discussion of stacks in the context of this assignment is given here.

Restrictions: Your program should not make any a priori assumptions about how large input expressions can be, and thus how deep the evaluation stack needs to be; instead, memory for the stack should be dynamically allocated. I would like you to get practice with pointers, so you should not use realloc() for this. Solutions that preallocate a fixed amount of memory, or which dynamically resize an array using realloc(), will not receive credit.

You should also not make assumptions about the length of the input line. Instead, use getline() to read in the input: see here for detaiils. This program has an example of the use of getline().

Input tokenization: The string library routine strtok() can be used to tokenize a line read in from the input; see man strtok. An example of its usage is shown here.

While strtok() will divide up a string into a sequence of tokens, it will not compute the numerical value of a sequence of digits. For this, you can use the library function strtol(); see man strtol. (The function atoi() is a simpler and commonly-used alternative, but this function is unable to detect errors: for example, if strtok() finds a token "123abc", atoi() will give the value 123 but will not indicate that the token contains invalid characters; strtol() can be used to detect this.)

Error conditions: The following are errors:

An error in memory allocation. If one occurs, give an error message and exit.

Illegal characters in the input. An error in evaluating an expression, e.g., due to an insufficient number of operands for any operator. Too many operands in the input (the stack contains more than one value at the end after evaluation is complete). If any of these occurs, give an error message, ignore the corresponding line, and continue processing.

Makefile: In addition to your source files, you should submit a make file named Makefile that supports at least the following functionality:

make rpn

Compiles the C source code to create an executable named rpn. The compiler options used should include -Wall.

make clean (phony target)

Deletes all object files (*.o), if any, as well as the executable rpn).

Submitting your assignment: Collect all of the files related to this assignment, as described below, into a directory named rpn and use the turnin command to submit this directory (this will cause all of the files in the directory to be submitted). The directory rpn should contain:

the C source code (including source file and, if any, header file) for your program;

A makefile, as described above;

Explanation / Answer

here is your answer : ------------>>>>>>>>>>>>

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define true 1
#define false 0
#define error 2
#define bool int

typedef struct Node_{
long val;
struct Node_ *next;
}Node;

long pop(Node **root){
if(*root == NULL){
  return 0;
}
Node *cur = *root;
*root = (*root)->next;
long v = cur->val;
free(cur);
return v;
}

void push(Node **root,long val){
if(*root == NULL){
  *root = (Node *)malloc(sizeof(Node));
  (*root)->val = val;
  (*root)->next = NULL;
  return;
}
Node *cur = (Node *)malloc(sizeof(Node));
cur->val = val;
cur->next = *root;
*root = cur;
}

void getInput(char **str){
*str = (char *)malloc(sizeof(char) * 500);
printf(" Enter The RPN Expression = ");
fgets(*str,500,stdin);
}

bool isNumber(char *ch){
char *ptr = NULL;
long val;
val = strtol(ch,&ptr,10);
if(val == 0){
  return false;
}
if(ptr[0] == ''){
  return true;
}
return error;
}

bool isOperator(char *ch){
char *ptr = NULL;
long val;
val = strtol(ch,&ptr,10);
if(val != 0){
  return error;
}
if(ptr[0] == ''){
  return error;
}
if(ptr[0] == '+' || ptr[0] == '-' || ptr[0] == '/' || ptr[0] == '*'){
  return true;
}
return false;
}

int main(){
char *str;
getInput(&str);
char *word;
Node *root = NULL;
long op1,op2,val;

word = strtok(str," ");
while(word != NULL){
  if(isNumber(word) == error){
   printf(" Input Error !!! ");
   return -1;
  }
  if(isNumber(word) == true){
   push(&root,(long)atoi(word));
  }else if(isOperator(word) == true){
   if(root == NULL){
    printf(" Wrong RPN Expression ");
    return -1;
   }
   op1 = pop(&root);
   if(root == NULL){
    printf(" Wrong RPN Expression ");
    return -1;
   }
   op2 = pop(&root);
   switch(word[0]){
    case '+':val = op1 + op2;break;
    case '*':val = op1 * op2;break;
    case '-':val = op1 - op2;break;
    case '/':val = op1 / op2;break;
   }
   push(&root,val);
  }else{
   printf(" Error Occured in Input !!!! ");
   return -1;
  }
  word = strtok(NULL," ");
}
if(root == NULL){
  printf(" An Error Occured in Input ");
  return -1;
}
if(root->next != NULL){
  printf(" Worng RPN Expression");
}else{
  printf(" Result = %ld ",root->val);
}

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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