Question

Q5 - 15 pts) You are given the code (including the main function) for evaluating an expression that is input in the postfix format. You will modify the code in the main function so that it can evaluate an expression that is input in the prefix format and print the intermediate results as well as the final result of the evaluation. You should also test your code with an expression string in prefix format that comprises of all the four operators (at least once) in a randomly chosen order with randomly chosen values in the range 10 to 50. For example, a sample expression string (prefix notation) could be input as -, +, *, /, 15, 12, 23, 44, 38 for the expression (infix notation) 15 / 12 * 23 + 44 - 38.

CODE in C++:

#include <iostream>

#include <string>

#include <cstring>

using namespace std;

class Node{

private:

int data;

Node* nextNodePtr;

Node* prevNodePtr;

public:

Node(){}

void setData(int d){

data = d;

}

int getData(){

return data;

}

void setNextNodePtr(Node* nodePtr){

nextNodePtr = nodePtr;

}

Node* getNextNodePtr(){

return nextNodePtr;

}

void setPrevNodePtr(Node* nodePtr){

prevNodePtr = nodePtr;

}

Node* getPrevNodePtr(){

return prevNodePtr;

}

};

class Stack{

private:

Node* headPtr;

Node* tailPtr;

public:

Stack(){

headPtr = new Node();

tailPtr = new Node();

headPtr->setNextNodePtr(0);

tailPtr->setPrevNodePtr(0);

}

Node* getHeadPtr(){

return headPtr;

}

Node* getTailPtr(){

return tailPtr;

}

bool isEmpty(){

if (headPtr->getNextNodePtr() == 0)

return true;

return false;

}

void push(int data){

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(0);

Node* lastNodePtr = tailPtr->getPrevNodePtr();

if (lastNodePtr == 0){

headPtr->setNextNodePtr(newNodePtr);

newNodePtr->setPrevNodePtr(0);

}

else{

lastNodePtr->setNextNodePtr(newNodePtr);

newNodePtr->setPrevNodePtr(lastNodePtr);

}

tailPtr->setPrevNodePtr(newNodePtr);

}

int pop(){

Node* lastNodePtr = tailPtr->getPrevNodePtr();

Node* prevNodePtr = 0;

int poppedData = -100000; //empty stack

if (lastNodePtr != 0){

prevNodePtr = lastNodePtr->getPrevNodePtr();

poppedData = lastNodePtr->getData();

}

else

return poppedData;

if (prevNodePtr != 0){

prevNodePtr->setNextNodePtr(0);

tailPtr->setPrevNodePtr(prevNodePtr);

}

else{

headPtr->setNextNodePtr(0);

tailPtr->setPrevNodePtr(0);

}

return poppedData;

}

int peek(){

Node* lastNodePtr = tailPtr->getPrevNodePtr();

if (lastNodePtr != 0)

return lastNodePtr->getData();

else

return -100000; // empty stack

}

};

int main(){

Stack stack;

string expression;

cout << "Enter the expression to evaluate: ";

getline(cin, expression);

char* expressionArray = new char[expression.length()+1];

strcpy(expressionArray, expression.c_str());

char* cptr = strtok(expressionArray, ", ");

while (cptr != 0){

string token(cptr);

bool isOperator = false;

if ( (token.compare("*") == 0) || (token.compare("/") == 0) || (token.compare("+") == 0) || (token.compare("-") == 0) )

isOperator = true;

if (!isOperator){

int val = stoi(token);

stack.push(val);

}

if (isOperator){

int rightOperand = stack.pop();

int leftOperand = stack.pop();

if (token.compare("*") == 0){

int result = leftOperand * rightOperand;

cout << "intermediate result: " << result << endl;

stack.push(result);

}

else if (token.compare("/") == 0){

int result = leftOperand / rightOperand;

cout << "intermediate result: " << result << endl;

stack.push(result);

}

else if (token.compare("+") == 0){

int result = leftOperand + rightOperand;

cout << "intermediate result: " << result << endl;

stack.push(result);

}

else if (token.compare("-") == 0){

int result = leftOperand - rightOperand;

cout << "intermediate result: " << result << endl;

stack.push(result);

}

}

cptr = strtok(NULL, ", ");

}

cout << "final result: " << stack.pop() << endl;

return 0;

}

Answer 1

#include <cstring>
#include<bits/stdc++.h>
using namespace std;

class Node
{
    private:
        int data;
        Node* nextNodePtr;
        Node* prevNodePtr;
    public:
        Node(){}
        void setData(int d)
        {
            data = d;
        }
        int getData()
        {
            return data;
        }
        void setNextNodePtr(Node* nodePtr)
        {
            nextNodePtr = nodePtr;
        }
        Node* getNextNodePtr()
        {
            return nextNodePtr;
        }
        void setPrevNodePtr(Node* nodePtr)
        {
            prevNodePtr = nodePtr;
        }
        Node* getPrevNodePtr()
        {
            return prevNodePtr;
        }

};

class Stack
{
    private:
        Node* headPtr;
        Node* tailPtr;
    public:
        Stack()
        {
            headPtr = new Node();
            tailPtr = new Node();
            headPtr->setNextNodePtr(0);
            tailPtr->setPrevNodePtr(0);
        }
        Node* getHeadPtr()
        {
            return headPtr;
        }
        Node* getTailPtr()
        {
            return tailPtr;
        }
        bool isEmpty()
        {
            if (headPtr->getNextNodePtr() == 0)
                return true;
            return false;
        }
        void push(int data)
        {
            Node* newNodePtr = new Node();
            newNodePtr->setData(data);
            newNodePtr->setNextNodePtr(0);
            Node* lastNodePtr = tailPtr->getPrevNodePtr();
            if (lastNodePtr == 0)
            {
                headPtr->setNextNodePtr(newNodePtr);
                newNodePtr->setPrevNodePtr(0);
            }
            else
            {
                lastNodePtr->setNextNodePtr(newNodePtr);
                newNodePtr->setPrevNodePtr(lastNodePtr);
            }
            tailPtr->setPrevNodePtr(newNodePtr);
        }
        int pop()
        {
            Node* lastNodePtr = tailPtr->getPrevNodePtr();
            Node* prevNodePtr = 0;
            int poppedData = -100000; //empty stack
            if (lastNodePtr != 0)
            {
                prevNodePtr = lastNodePtr->getPrevNodePtr();
                poppedData = lastNodePtr->getData();
            }
            else
                return poppedData;
            if (prevNodePtr != 0)
            {
                prevNodePtr->setNextNodePtr(0);
                tailPtr->setPrevNodePtr(prevNodePtr);
            }
            else
            {
                headPtr->setNextNodePtr(0);
                tailPtr->setPrevNodePtr(0);
            }
            return poppedData;
        }
        int peek()
        {
            Node* lastNodePtr = tailPtr->getPrevNodePtr();
            if (lastNodePtr != 0)
                return lastNodePtr->getData();
            else
                return -100000; // empty stack
        }
};

int main()
{
    int i;
    Stack stack1;
    string expression;
    cout << "Enter the expression to evaluate: ";
    getline(cin, expression);
    char* expressionArray = new char[expression.length()+1];
    strcpy(expressionArray, expression.c_str());
    char* cptr = strtok(expressionArray, ", ");
    vector<string> v;
    while(cptr!=NULL)
    {
        v.push_back(cptr);
       // cout<<cptr<<" ";
        cptr =strtok(NULL, ", ");
    }
    cout<<endl;
    stack <string> s;
  
    for(i=v.size()-1;i>=0;i--)
    {
        //cout<<v[i]<<" ";
        if((v[i]!="*")&&(v[i]!="/")&&(v[i]!="+")&&(v[i]!="-"))
        {
            v[i]+=",";
            s.push(v[i]);
        }
        else
        {
            string s3;
            string s1,s2;
            s1=s.top();
            s.pop();
            s2=s.top();
            s.pop();
            s3=s1+s2+v[i]+",";
            s.push(s3);
        }
    }
    //cout<<endl;
    string str=s.top();
    s.pop();
    strcpy(expressionArray, str.c_str());
    cptr = strtok(expressionArray, ", ");
    while (cptr != 0)
    {
        string token(cptr);
        bool isOperator = false;
        if ( (token.compare("*") == 0) || (token.compare("/") == 0) || (token.compare("+") == 0) || (token.compare("-") == 0) )
            isOperator = true;
        if (!isOperator)
        {
            int val = stoi(token);
            stack1.push(val);
        }
        if (isOperator)
        {
            int rightOperand = stack1.pop();
            int leftOperand = stack1.pop();
            if (token.compare("*") == 0)
            {
                int result = leftOperand * rightOperand;
                cout << "intermediate result: " << result << endl;
                stack1.push(result);
            }
            else if (token.compare("/") == 0)
            {
                int result = leftOperand / rightOperand;
                cout << "intermediate result: " << result << endl;
                stack1.push(result);
            }
            else if (token.compare("+") == 0)
            {
                int result = leftOperand + rightOperand;
                cout << "intermediate result: " << result << endl;
                stack1.push(result);
            }
            else if (token.compare("-") == 0)
            {
                int result = leftOperand - rightOperand;
                cout << "intermediate result: " << result << endl;
                stack1.push(result);
            }
        }
        cptr = strtok(NULL, ", ");
    }
    cout << "final result: " << stack1.pop() << endl;
    return 0;
}