Implement a Reverse Polish Notation calculator that can perform addition, subtraction, multiplication and division on integers, using a stack.
The implementation should parse the input string and push the operands onto stack and when it encounters an operation, it should pop the operands from the stack, evaluate the result and push the result back onto the stack. Eg: If passed "21 13 + 40 - 12 / 2 *" the answer returned should be 4. The above string should be evaluated as 2 * (12 / (40 - (21 + 13)))
/*
* RPNCalc.cpp
*
* Created on: Apr 5, 2012
* Author: khegde
*/
#include <string>
#include <iostream>
#include <string>
#include <cstring>
#include <stdio.h>
using namespace std;
/**
* Node containing integer data
*/
struct Node {
int data;
Node *next;
};
/**
* A stack class
*/
class Stack {
public:
Stack() {
top = NULL;
}
~Stack() {
while (top != NULL) {
Node * temp = top->next;
delete top;
top = temp;
}
}
int pop() {
if (top == NULL)
return 0;
Node *temp = top;
int retVal = top->data;
top = top->next;
delete temp;
return retVal;
}
void push(int n) {
Node *temp = new Node();
temp->data = n;
temp->next = top;
top = temp;
}
int peek() {
if (top == NULL)
return 0;
return top->data;
}
void print() {
Node *temp = top;
cout << "Stack: " ;
while (top != NULL) {
cout << top->data << "-->";
top = top->next;
}
cout << "EMPTY" << endl;
top = temp;
}
private:
Node *top;
};
/**
* A tokenizer class used to tokenize a string based on whitespace chars
*/
class Tokenizer {
public:
Tokenizer(string &s) {
m_str = s;
p_ch = strtok((char *) m_str.c_str(), " ");
}
char *getToken() {
return p_ch;
}
bool next() {
p_ch = strtok(NULL, " ");
if (p_ch == NULL)
return false;
return true;
}
bool isValue() {
bool retVal = false;
if (sscanf(p_ch, "%d", &m_int) > 0)
retVal = true;
return retVal;
}
int getValue() {
return m_int;
}
private:
string m_str;
int m_int;
char *p_ch;
};
/**
* Reverse Polish Notation Calculator class
*/
class RPNCalc {
public:
RPNCalc(string &s) {
m_tok = new Tokenizer(s);
m_stack = new Stack;
}
virtual ~RPNCalc() {
delete m_tok;
delete m_stack;
}
int eval() {
while (m_tok->getToken() != NULL) {
if (m_tok->isValue()) {
m_stack->push(m_tok->getValue());
} else {
int v1 = m_stack->pop();
int v2 = m_stack->pop();
m_stack->push(calc(v1, v2, m_tok->getToken()));
}
m_tok->next();
}
return m_stack->pop();
}
private:
Stack *m_stack;
Tokenizer *m_tok;
int calc(int v1, int v2, char *op) {
int retVal = 0;
switch (op[0]) {
case '+':
retVal = v1 + v2;
break;
case '-':
retVal = v1 - v2;
break;
case '*':
retVal = v1 * v2;
break;
case '/':
retVal = v1 / v2;
break;
default:
cout << "invalid op" << op[0] << endl;
break;
}
return retVal;
}
};
/**
* Test the program
*/
int main() {
std::string s = "21 13 + 40 - 12 / 2 *";
RPNCalc rpn(s);
cout << rpn.eval() << endl; // 2 * (12 / (40 - (21 + 13))) = 4
return 0;
}