RPN Expression Calculator Simulation
#pragma once
#include
#include"StackADT.h"
template
class LinkedStack : public StackADT
{
// inner struct represnets the linked list node structure
struct Node{
T data;
Node* next;
};
Node* head; // head of the linkedlist
Node* tail; // tail of the linkedlist
int size; // number of elements in the list
void printHelper(Node * node); // recursion function to help print stack
public:
LinkedStack();
void push(const T& data); // push data into stack
void pop(); // pop data from the stack
T top(); // peek the top of the stack
bool isEmpty(); // check if the stack is already empty
int getSize(); // returns the size of the stack
void print(); // prints all the elements in the stack
bool isFull();
~LinkedStack(); // delete all elements in the stack to not cause a memory leak
};
template
LinkedStack::LinkedStack()
{
head = nullptr;
size = 0;
}
template
void LinkedStack::push(const T& data){
size++;
if (head == nullptr){
// if the list is already empty
head = new Node();
head->data = data;
head->next = nullptr;
tail = head;
return;
}
Node* cur = head;
while (cur->next != nullptr)
{
// iterate to the last element in the list
cur = cur->next;
}
// append data to the end of the list
cur->next = new Node();
cur->next->data = data;
cur->next->next = nullptr;
tail = cur->next;
return;
}
template
void LinkedStack::pop(){
assert(size > 0);
// pop function is to delete last node in the list
size--;
if (head == tail){
// one element list => delete the head only
delete head;
head = tail = nullptr;
return;
}
Node *cur = head;
while (cur->next != tail){
// search for the last element in the list
cur = cur->next;
}
// delete that element
delete cur->next;
cur->next = nullptr;
tail = cur;
return;
}
template
T LinkedStack::top(){
assert(size > 0);
return tail->data;
}
template
int LinkedStack::getSize(){
return size;
}
template
bool LinkedStack::isEmpty(){
return size == 0;
}
template
LinkedStack::~LinkedStack(){
if (size == 0){
return;
}
// clears the memory so no memory leaks can happen
if (head->next == nullptr){
// one element list => just delete the head.
delete head;
return;
}
Node * cur = head;
Node* temp;
// iterate over the list and delete element by element
while (cur->next != nullptr){
temp = cur->next->next;
delete cur->next;
cur = temp;
}
delete cur;
delete head;
}
template
void LinkedStack::print(){
if (head == nullptr){
// empty list print
cout << "<>"<"<
void LinkedStack::printHelper(Node * node){
if (node->next == nullptr){
cout << node->data;
return;
}
printHelper(node->next);
cout << ", " << node->data;
}
template
bool LinkedStack::isFull(){
return !isEmpty();
}
StackADT.h
#ifndef STACK_ADT
#define STACK_ADT
template
class StackADT{
//Function to add a new item to the stack
//Precondition: Stack exists and is not full
//Post Condition: Stack is changed and the new item
//is added to the top of the stack
virtual void push(const T&) = 0;
//Function to remove the top element from the stack
//Precondition: Stack exists and is not empty
//Post Condition: Stack is changed and the top element is removed from the stack
virtual void pop() = 0;
//Function to return the top element from the stack
//Precondition: Stack exists and is not empty
//Post Condition: If the stack is empty, the program returns, otherwise,
//the top element of the stack is returned
virtual T top() = 0;
//Function to determine whether the stack is empty
//Post Condition: Returns 1 of the stack is empty
//otherwise returns 0
virtual bool isEmpty() = 0;
//Function to determine whether the stack is full
//Post Condition: Returns 1 of the stack is full
//otherwise returns 0
virtual bool isFull() = 0;
};
#endif
Source.cpp
#define _CRT_SECURE_NO_WARNINGS
#include"LinkedStack.h"
#include
#include
using namespace std;
// Returns true if all the chars in the token is zeros. this function used to differentiate between
// the atoi result zeros for bad parsing or actual zero.
bool isZero(char* tok){
for (int i = 0; i < strlen(tok); i++){
if (tok[i] != '0'){
return false;
}
}
return true;
}
// Returns true if all the chats in the tokens are numbers. this function is used to differntitate between
// total correct int num and not completly correct ones(as atoi function returs 15 for both '15' and '15.625')
bool totalNumber(char*tok){
for (int i = 0; i < strlen(tok); i++){
if (tok[i] < '0' || tok[i] > '9'){
return false;
}
}
return true;
}
int main(){
LinkedStack stack;
string exp; // total expression from user
char tok[30]; // token taken from the expression
int num,num2; // numbers holders for operations
bool exit = false;
int res; // final result tracker
cout << "Enter the expression: ";
getline(cin,exp);
while (!exit){
// these next three lines used to extract the next token from the expression
sscanf(exp.c_str(), "%s ", &tok);
if (strlen(tok) + 1 < exp.size())
exp = exp.substr(strlen(tok)+1);
// work with token "tok"
num = atoi(tok);
if (num != 0){
// check if number is totally correct integer number
if (!totalNumber(tok)){
cout << "invalid input" << endl;
continue;
}
stack.push(num);
}
else if (isZero(tok)){
// to differntiate between the zero from atoi when bad parsing happen
// or when an actual zero is passed
stack.push(0);
}
else if (strcmp(tok, "<<") == 0){
stack.print();
}
else if (strcmp(tok, "^") == 0){
cout<