postfix Scheme is prefix language, where the first element of a list is assumed

ID: 3718932 • Letter: P

Question

postfix Scheme is prefix language, where the first element of a list is assumed to be an operator. Write

a postfix interpreter in scheme, where the operator comes last in the list. Your interpreter should be able to handle +, -, * and /. If the argument is not a list, simply return the argument. If the argument is a list, it will have exactly three elements. Note that the argument may be nested. Example how it should run Below.

> (postfix '(3 5 +))

(postfix '(5 3 *))

> (postfix '(5 (3 1 +) *))

> (postfix 3)

Explanation / Answer

// C program to evaluate value of a postfix expression

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include <stdlib.h>

// <a href="#">Stack</a> type

struct <a href="#">Stack</a>

{

int top;

unsigned capacity;

int* array;

};

// <a href="#">Stack</a> Operations

struct <a href="#">Stack</a>* createStack( unsigned capacity )

struct <a href="#">Stack</a>* <a href="#">stack</a> = (struct <a href="#">Stack</a>*) malloc(sizeof(struct <a href="#">Stack</a>));

if (!<a href="#">stack</a>) return NULL;

<a href="#">stack</a>->top = -1;

<a href="#">stack</a>->capacity = capacity;

<a href="#">stack</a>->array = (int*) malloc(<a href="#">stack</a>->capacity * sizeof(int));

if (!<a href="#">stack</a>->array) return NULL;

return <a href="#">stack</a>;

}

int isEmpty(struct <a href="#">Stack</a>* <a href="#">stack</a>)

{

return <a href="#">stack</a>->top == -1 ;

}

char peek(struct <a href="#">Stack</a>* <a href="#">stack</a>)

{

return <a href="#">stack</a>->array[<a href="#">stack</a>->top];

}

char pop(struct <a href="#">Stack</a>* <a href="#">stack</a>)

{

if (!isEmpty(<a href="#">stack</a>))

return <a href="#">stack</a>->array[<a href="#">stack</a>->top--] ;

return '$';

}

void push(struct <a href="#">Stack</a>* <a href="#">stack</a>, char op)

{

<a href="#">stack</a>->array[++<a href="#">stack</a>->top] = op;

}

// The main function that returns value of a given postfix expression

int evaluatePostfix(char* exp)

{

// Create a <a href="#">stack</a> of capacity equal to expression size

struct <a href="#">Stack</a>* <a href="#">stack</a> = createStack(strlen(exp));

int i;

// See if <a href="#">stack</a> was created successfully

if (!<a href="#">stack</a>) return -1;

// Scan all characters one by one

for (i = 0; exp[i]; ++i)

{

// If the scanned character is an operand (number here),

// push it to the <a href="#">stack</a>.

if (isdigit(exp[i]))

push(<a href="#">stack</a>, exp[i] - '0');

// If the scanned character is an operator, pop two

// elements from <a href="#">stack</a> apply the operator

else

{

int val1 = pop(<a href="#">stack</a>);

int val2 = pop(<a href="#">stack</a>);

switch (exp[i])

{

case '+': push(<a href="#">stack</a>, val2 + val1); break;

case '-': push(<a href="#">stack</a>, val2 - val1); break;

case '*': push(<a href="#">stack</a>, val2 * val1); break;

case '/': push(<a href="#">stack</a>, val2/val1); break;

}

return pop(<a href="#">stack</a>);

}

// Driver program to test above functions

int main()

{

char exp[] = "231*+9-";

printf ("postfix %s ", exp);

printf("%d",evaluatePostfix(exp));

return 0;

}