C++ Data Structures with Templates
Chapter 4: A Stack Class
The Code
Stack.h#ifndef Stack_H
#define Stack_H
template<typename T>
class Stack {
public:
Stack();
~Stack();
void push(const T);
T pop();
T peek();
size_t stackCount();
bool empty();
private:
bool isFull();
void resize(size_t);
static const size_t defSize = 4;
T* stackPointer;
T noT;
size_t sSize, top, tSize;
};
template<typename T>
Stack<T>::Stack() {
top = 0;
tSize = sizeof(T);
stackPointer = (T*)malloc(tSize * defSize);
if (stackPointer == NULL) {
sSize = 0;
}
sSize = defSize;
memset(&noT, 0, tSize);
}
template<typename T>
Stack<T>::~Stack() {
free(stackPointer);
}
template<typename T>
void Stack<T>::push(const T t) {
if (isFull()) {
resize(sSize * 2);
}
stackPointer[top++] = t;
}
template<typename T>
T Stack<T>::pop() {
if (empty()) {
return noT;
}
T t = stackPointer[--top];
// think about resizing
if (top <= sSize / 4 && sSize > defSize) {
resize(sSize / 2);
}
return t;
}
template<typename T>
T Stack<T>::peek() {
if (empty()) {
return noT;
}
else {
T t = stackPointer[top - 1];
return t;
}
}
template<typename T>
size_t Stack<T>::stackCount() {
return top;
}
template<typename T>
bool Stack<T>::empty() {
return (top == 0);
}
template<typename T>
bool Stack<T>::isFull() {
return (top == sSize);
}
template<typename T>
void Stack<T>::resize(size_t newSize) {
T* tempP = (T *)realloc(stackPointer, tSize * newSize);
if (tempP) {
stackPointer = tempP;
sSize = newSize;
}
}
#endif
Stack.cpp
#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include "Stack.h"
#include <iostream>
#include "Stackh.h"
using namespace std;
#define OPCOUNT 6
#define MAXTOKENS 30
#define BUFFSIZE 133
void processExpr();
uint8_t findNextToken(bool);
uint8_t validateExp();
double evalExp();
double doArith(uint8_t, double, double);
void displayError();
enum Tokens {
LEFTPAREN, // order in sequence of (, +, -, * and / is required
PLUS, // as a proxy for arithmetic precedence
MINUS,
MULTIPLY,
DIVIDE,
RIGHTPAREN,
NUM,
OPERATOR,
ERRORTOKEN
};
struct keyname {
char* keyword;
uint8_t token;
};
const keyname operators[OPCOUNT] = {
{ "+", PLUS },
{ "-", MINUS },
{ "*", MULTIPLY },
{ "/", DIVIDE },
{ "(", LEFTPAREN },
{ ")", RIGHTPAREN }
};
struct StatItem {
uint8_t sType;
union {
double fVal;
uint8_t iVal;
};
};
uint8_t statItemCount, errCode;
StatItem statItems[MAXTOKENS];
char buff[BUFFSIZE];
char *pptr, *nptr;
int main()
{
cout << "Enter an expression\n";
while (true) {
cin.getline(buff, 132);
processExpr();
cout << "Another?\n";
}
return 0;
}
void processExpr() {
if (strlen(buff) == 0) {
return;
}
if (strlen(buff) == 0) { return; }
pptr = nptr = buff;
statItemCount = 0;
bool lastWasOp = true;
uint8_t tkn = findNextToken(lastWasOp);
while (tkn != ERRORTOKEN && statItemCount <= MAXTOKENS) {
lastWasOp = false;
switch (tkn) {
case NUM:
statItems[statItemCount].sType = tkn;
statItems[statItemCount].fVal = atof(pptr);
break;
default:
statItems[statItemCount].sType = OPERATOR;
statItems[statItemCount].iVal = tkn;
lastWasOp = true;
break;
}
statItemCount++;
pptr = nptr;
tkn = findNextToken(lastWasOp);
}
errCode = validateExp();
if (errCode == 0) {
double res = evalExp();
if (errCode == 0) {
// no evaluation error
cout << "Evaluates to: " << res << '\n';
}
}
if (errCode != 0) {
displayError();
}
}
uint8_t findNextToken(bool wasOp) {
// we are looking for constants and operators
// ignore whitespace between statement components
while (isspace(*pptr)) {
pptr++;
}
if (*pptr == 0) {
return ERRORTOKEN;
}
if (isdigit(*pptr) || (*pptr == '-' && wasOp) || *pptr == '.') {
bool isNum = false;
int i = (isdigit(*pptr)) ? 0 : 1;
for (int j = strlen(pptr); i < j; i++) {
if (isdigit(pptr[i]) || pptr[i] == '.') {
isNum = true;
nptr = pptr + i;
}
else { break; }
}
if (isNum) {
nptr++;
return NUM;
}
}
for (int k = 0; k < OPCOUNT; k++) {
if (strncmp(pptr, operators[k].keyword, strlen(operators[k].keyword)) == 0) {
nptr = pptr + strlen(operators[k].keyword);
return operators[k].token;
}
}
return ERRORTOKEN;
}
uint8_t validateExp() {
int pCount = 0;
int tr = 0;
bool wasOp = true;
for (int i = 0; i < statItemCount; i++) {
int st = statItems[i].sType;
int tk = statItems[i].iVal;
if (st == OPERATOR) {
if (tk == LEFTPAREN) { pCount++; continue; }
if (tk == RIGHTPAREN) { pCount--; continue; }
if (wasOp) { return 3; }
wasOp = true;
}
if (st == NUM) {
if (!wasOp) {
return 5;
}
wasOp = false;
}
}
if (pCount != 0) {
return 7;
}
if (wasOp) {
return 6; // op without value
}
return 0;
}
double evalExp() {
Stack<int> opStack;
Stack<double> valStack; // create a value stack and operator stack
int op;
float r, l;
for (int i = 0; i < statItemCount; i++) {
if (statItems[i].sType == NUM) {
valStack.push(statItems[i].fVal);
continue;
}
if (statItems[i].sType == OPERATOR) {
if (statItems[i].iVal == LEFTPAREN) {
opStack.push(LEFTPAREN);
continue;
}
if (statItems[i].iVal == RIGHTPAREN) {
while (opStack.peek() != LEFTPAREN) {
op = opStack.pop();
r = valStack.pop();
l = valStack.pop(); // get the order right before left
valStack.push(doArith(op, l, r));
}
opStack.pop(); //remove the left paren
continue;
}
// another operator
while (opStack.stackCount() > 0) {
if (opStack.peek() >= statItems[i].iVal) {
// while any existing operators have higher precedence
op = opStack.pop();
r = valStack.pop();
l = valStack.pop(); // get the order right before left
valStack.push(doArith(op, l, r));
}
else {
break;
}
}
opStack.push(statItems[i].iVal); // push the new op
}
}
// work back through the stack
while (opStack.stackCount() > 0) {
op = opStack.pop();
r = valStack.pop();
l = valStack.pop();
valStack.push(doArith(op, l, r));
}
return valStack.pop();
}
double doArith(uint8_t op, double lVal, double rVal) {
switch (op) {
case MULTIPLY:
return lVal * rVal;
case DIVIDE:
if (rVal == 0) {
errCode = 21;
return 0;
}
return lVal / rVal;
case MINUS:
return lVal - rVal;
case PLUS:
return lVal + rVal;
default:
return 0;
}
}
void displayError() {
switch (errCode) {
case 3:
cout << "Operator does not follow a value\n";
break;
case 5:
cout << "Expression is missing an operator\n";
break;
case 6:
cout << "Incomplete expression\n";
break;
case 7:
cout << "Missing parenthasis\n";
break;
case 21:
cout << "Divide by zero error\n";
break;
default:
cout << "Undefined error\n";
break;
}
}
Stack.ino
#include "Stack.h"
#define OPCOUNT 6
#define MAXTOKENS 30
#define BUFFSIZE 133
enum Tokens {
LEFTPAREN, // order in sequence of (, +, -, * and / is required
PLUS, // as a proxy for arithmetic precedence
MINUS,
MULTIPLY,
DIVIDE,
RIGHTPAREN,
NUM,
OPERATOR,
ERRORTOKEN
};
struct keyname {
const char* keyword;
uint8_t token;
};
const keyname operators[OPCOUNT] = {
{"+", PLUS},
{"-", MINUS},
{"*", MULTIPLY},
{"/", DIVIDE},
{"(", LEFTPAREN},
{")", RIGHTPAREN}
};
struct statItem {
uint8_t sType;
union{
float fVal;
uint8_t iVal;
};
};
uint8_t statItemCount, errCode;
statItem statItems[MAXTOKENS];
char buff[BUFFSIZE];
int buffPos = 0;
char *pptr, *nptr;
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; }
void setup() {
Serial.begin(115200);
memset(buff, '\0', BUFFSIZE);
Serial.println("Send an expression:");
}
void loop() {
if(Serial.available()) {
char c = Serial.read();
switch(c) {
case 10:
case 13:
processExpr();
break;
default:
if(buffPos <= BUFFSIZE-1) {
buff[buffPos++] = c;
}
}
}
}
void processExpr() {
if (strlen(buff) == 0) {return;}
pptr = nptr = buff;
statItemCount = 0;
bool lastWasOp = true;
uint8_t tkn = findNextToken(lastWasOp);
while (tkn != ERRORTOKEN && statItemCount <= MAXTOKENS) {
lastWasOp = false;
switch(tkn) {
case NUM:
statItems[statItemCount].sType = tkn;
statItems[statItemCount].fVal = atof(pptr);
break;
default:
statItems[statItemCount].sType = OPERATOR;
statItems[statItemCount].iVal = tkn;
lastWasOp = true;
break;
}
statItemCount++;
pptr = nptr;
tkn = findNextToken(lastWasOp);
}
errCode = validateExp();
if (errCode == 0) {
float res = evalExp();
Serial.println(buff);
if(errCode == 0){
Serial.print("Evaluates to: ");
int ri = res;
if(res-ri == 0.0) {
Serial.println(ri);
} else {
Serial.println(res, 5);
}
}
}
if(errCode != 0) {
displayError();
}
buffPos = 0;
memset(buff, '\0', BUFFSIZE);
Serial.println("Send another expression?");
}
uint8_t findNextToken(bool wasOp){
// we are looking for constants and operators
// ignore whitespace between statement components
while(isWhitespace(*pptr)) {
pptr++;
}
if(*pptr == 0) {
return ERRORTOKEN;
}
if(isdigit(*pptr) || (*pptr == '-' && wasOp) || *pptr == '.') {
bool isNum = false;
int i = (isdigit(*pptr)) ? 0 : 1;
for(int j = strlen(pptr); i < j; i++) {
if (isdigit(pptr[i]) || pptr[i] == '.') {
isNum = true;
nptr = pptr + i;
} else {break;}
}
if(isNum) {
nptr++;
return NUM;
}
}
for(int k = 0; k < OPCOUNT; k++) {
if(strncmp(pptr, operators[k].keyword, strlen(operators[k].keyword)) == 0) {
nptr = pptr + strlen(operators[k].keyword);
return operators[k].token;
}
}
return ERRORTOKEN;
}
int validateExp() {
int pCount = 0;
int tr = 0;
bool wasOp = true;
for(int i = 0; i < statItemCount; i++) {
int st = statItems[i].sType;
int tk = statItems[i].iVal;
if(st == OPERATOR){
if(tk == LEFTPAREN) {pCount++; continue;}
if(tk == RIGHTPAREN) {pCount--; continue;}
if(wasOp) {return 3;}
wasOp = true;
}
if(st == NUM) {
if(!wasOp) {
return 5;
}
wasOp = false;
}
}
if(pCount != 0) {
return 7;
}
if(wasOp) {
return 6; // op without value
}
return 0;
}
float evalExp() {
Stack<int> opStack;
Stack<float> valStack; // create a value stack and operator stack
int op;
float r, l;
for(int i = 0; i < statItemCount; i++) {
if(statItems[i].sType == NUM) {
valStack.push(statItems[i].fVal);
continue;
}
if(statItems[i].sType == OPERATOR) {
if(statItems[i].iVal == LEFTPAREN) {
opStack.push(LEFTPAREN);
continue;
}
if(statItems[i].iVal == RIGHTPAREN) {
while(opStack.peek() != LEFTPAREN) {
op = opStack.pop();
r = valStack.pop();
l = valStack.pop(); // get the order right before left
valStack.push(doArith(op, l, r));
}
opStack.pop(); //remove the left paren
continue;
}
// another operator
while(opStack.stackCount() > 0) {
if(opStack.peek() >= statItems[i].iVal){
// while any existing operators have higher precedence
op = opStack.pop();
r = valStack.pop();
l = valStack.pop(); // get the order right before left
valStack.push(doArith(op, l, r));
} else {
break;
}
}
opStack.push(statItems[i].iVal); // push the new op
}
}
// work back through the stack
while(opStack.stackCount() > 0) {
op = opStack.pop();
r = valStack.pop();
l = valStack.pop();
valStack.push(doArith(op, l, r));
}
return valStack.pop();
}
float doArith(int op, float lVal, float rVal) {
switch(op) {
case MULTIPLY:
return lVal * rVal;
case DIVIDE:
if(rVal == 0) {
errCode = 21;
return 0;
}
return lVal / rVal;
case MINUS:
return lVal - rVal;
case PLUS:
return lVal + rVal;
default:
return 0;
}
}
void displayError() {
switch (errCode) {
case 3:
Serial << "Operator does not follow a value\n";
break;
case 5:
Serial << "Expression is missing an operator\n";
break;
case 6:
Serial << "Incomplete expression\n";
break;
case 7:
Serial << "Missing parenthesis\n";
break;
case 21:
Serial << "Divide by zero error\n";
break;
default:
Serial << "Undefined error\n";
break;
}
}
Read the chapter in my book C++ Data Structures with immediate download from Amazon