Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

#include #include using namespace std; const char SENTINEL = ';'; struct Node { int data; Node* link; }; class Stack { public : Stack(); //default

image text in transcribed

#include

#include

using namespace std;

const char SENTINEL = ';';

struct Node

{

int data;

Node* link;

};

class Stack

{

public:

Stack(); //default constructor

//initializes the stack to an empty stack

bool isEmpty() const; //this is a const function, meaning it cannot change any of the member variables

//returns true if the stack is empty, false otherwise

int top() const; //this is a const function, meaning it cannot change any of the member variables

//returns the value at the top of stack, does not modify the stack, does not check if the stack is empty or not

void push(int data);

//adds data to the top of stack

void pop();

//removes the top value of stack, does not return it, does nothing if the stack is empty

private:

Node* stackTop; //pointer to the head of a linked list

void headInsert(int data);

//precondition: stackTop points to the beginning of a list, could be an empty list

//postcondition: a new node with data is added to the beginning of the list, and stackTop points to the new node

void headRemove();

//precondition: stackTop points to the beginning of a list, could be an empty list

//postcondition: the first node of the list is removed, and stackTop points to the next node

};

bool isOperator(char c);

//precondition: c is initialized

//postcondition: returns true if c is '+', '-', '*' or '/'

int calculate(int o1, int o2, char op);

//precondition: o1 and o2 are initialized and op is an operator

//postcondition: returns op(o1, o2), e.g. if op is '-' then returns o1-o2

int charToInt(char c);

//precondition: c is a digit

//postcondition: returns the integer value of c

int main()

{

char in, ans;

Stack operandStack;

cout

cin >> in;

while(in != SENTINEL)

{

if(isOperator(in))

{

//pop two numbers from stack

int n1, n2;

if(operandStack.isEmpty())

{

cout

exit(1);

}

n2 = operandStack.top();

operandStack.pop();

if(operandStack.isEmpty())

{

cout

exit(1);

}

n1 = operandStack.top();

operandStack.pop();

//push the result of calculation to the top of operandStack

operandStack.push(calculate(n1, n2, in));

}

else

{

//push the number to the top of opernadStack

/*your code here*/

}

cin >> in;

}

//pop a number from the top of stack

int res;

res = operandStack.top();

operandStack.pop();

if(operandStack.isEmpty()) /othing left in the stack

cout

else //there are still numbers in the stack

cout

return 0;

}

Stack::Stack()

{

/*your code here*/

}

void Stack::headInsert(int data)

{

/*your code here*/

}

void Stack::headRemove()

{

/*your code here*/

}

bool Stack::isEmpty() const

{

/*your code here*/

}

int Stack::top() const

{

/*your code here*/

}

void Stack::pop()

{

/*your code here*/

}

void Stack::push(int data)

{

/*your code here*/

}

bool isOperator(char c)

{

return c == '+' || c == '-' || c == '*' || c == '/';

}

int calculate(int o1, int o2, char op)

{

/*your code here*/

}

int charToInt(char c)

{

return (static_castint>(c) - static_castint>('0'));

}

Postfix notation, is a mathematical notation in which operators follow their operands; for instance, to add 3 and 4, one would write 3 4 rather than 3 4 (infix notation). If there are multiple operations, operators are given immediately after their second operands; so, the expression written 3-4+5 in conventional notation would be written 3 4- 5 in postfix notation: 4 is first subtracted from 3, then 5 is added to the result. An advantage of postfix notation is that it removes the need for parentheses that are required by infix notation. While 3 - 4 x 5 can also be written 3 - (4 x 5), which is different from (3 -4) x 5, in postfix notation, the former could be written 3 4 5 x-, while the latter could be written 3 4-5 x 0r 5 3 4-x (from Wikipedia) Stacks can be used to evaluate expressions in postfix notations by following these steps: If a number is typed, push it on the stack. If an operation is typed, pop off two numbers from the stack, perform the operation, and push the result back on the stack. You should complete the Stack class and other functions in the template file (found on Carmen) so that when the user enters an expression in postfix notation, the program calculates and shows the result. In this assignment the user enters one-digit numbers only, but the result can be any integer. Only basic operations (i.e. +,-, /, *) are entered by the user and integer division is used in calculations. User input ends with a semicolon Postfix notation, is a mathematical notation in which operators follow their operands; for instance, to add 3 and 4, one would write 3 4 rather than 3 4 (infix notation). If there are multiple operations, operators are given immediately after their second operands; so, the expression written 3-4+5 in conventional notation would be written 3 4- 5 in postfix notation: 4 is first subtracted from 3, then 5 is added to the result. An advantage of postfix notation is that it removes the need for parentheses that are required by infix notation. While 3 - 4 x 5 can also be written 3 - (4 x 5), which is different from (3 -4) x 5, in postfix notation, the former could be written 3 4 5 x-, while the latter could be written 3 4-5 x 0r 5 3 4-x (from Wikipedia) Stacks can be used to evaluate expressions in postfix notations by following these steps: If a number is typed, push it on the stack. If an operation is typed, pop off two numbers from the stack, perform the operation, and push the result back on the stack. You should complete the Stack class and other functions in the template file (found on Carmen) so that when the user enters an expression in postfix notation, the program calculates and shows the result. In this assignment the user enters one-digit numbers only, but the result can be any integer. Only basic operations (i.e. +,-, /, *) are entered by the user and integer division is used in calculations. User input ends with a semicolon

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Processing Fundamentals, Design, and Implementation

Authors: David M. Kroenke, David J. Auer

14th edition

133876705, 9781292107639, 1292107634, 978-0133876703

More Books

Students also viewed these Databases questions