/* View on next files ->>>> on top ^^^^^^^*/
/**
* @file Token.h
*/
#ifndef TOKEN_H
#define TOKEN_H
#include <iostream>
/**
* Tag represents a categories of token types
*/
enum Tag { OPERATOR, OPERAND, LPAREN, RPAREN };
/**
* @brief Operator represents types of binary operations
*/
enum Operator { ADD, SUBTRACT, MULTIPLY, DIVIDE };
/**
* @brief A data structure to represent a token parsed from a string.
*/
struct Token {
/** a numeric value -- only valid if the tag is OPERAND */
double d;
/** an operator type -- only valid if the tag is OPERATOR */
Operator o;
/** the category of the token */
Tag tag;
};
/**
* @brief convert an Operator to a std::string
* @param o the operator
* @return a string representation of the operator
*/
std::string opToString(Operator o);
/**
* @brief An overloaded stream insertion operator for the Token type.
* @param os the output stream object
* @param t the Token to be inserted into the stream
* @return the same ostream that was passed in
*/
std::ostream& operator<<(std::ostream& os, const Token& t);
/**
* @brief parse a string representing a simple arithmetic expression
* into sequence of tokens.
* @param s the string to parse
* @return the result of parsing the string into tokens
*/
std::vector<Token> tokenize(std::string s);
#endif
/**
* @file PostfixCalculator.cpp
*/
#include "PostfixCalculator.h"
#include<stack>
#include<iostream>
#include<string>
double PostfixCalculator::eval(std::vector<Token> tokens) {
std::stack<double>s;
double num1,num2;
for(unsigned int i = 0; i < tokens.size(); i++){
if (tokens[i].tag == Tag::OPERAND){
s.push(tokens[i].d);
} else{
num2 = s.top();
s.pop();
num1 = s.top();
s.pop();
if (tokens[i].tag == OPERATOR){
if(tokens[i].o == ADD){
s.push(num1+num2);
} else if(tokens[i].o == SUBTRACT){
s.push(num1 - num2);
}else if(tokens[i].o == MULTIPLY){
s.push(num1 * num2);
} else if(tokens[i].o == DIVIDE){
s.push(num1 / num2);
}
}
}
}
return s.top();
}
/**
* @file PostfixCalculator.h
*/
#ifndef POSTFIX_CALCULATOR_H
#define POSTFIX_CALCULATOR_H
#include<vector>
#include "EvalInterface.h"
class PostfixCalculator : public EvalInterface<double>
{
public:
double eval(std::vector<Token> expr);
};
#endif
/**
* @file EvalInterface.h
*/
#ifndef EVAL_INTERFACE_H
#define EVAL_INTERFACE_H
#include <string>
#include "Token.h"
/**
* @brief The EvalInterface is an abstract class for evaluating
* different kinds of expressions.
*/
template <class T>
class EvalInterface
{
public:
/**
* @brief evaluate an expression represented as a sequence of tokens.
* @param expr the expression to evaluate
* @return the result of evaluating the expression
*/
virtual T eval(std::vector<Token> expr) = 0;
/**
* virtual destructor so subtype destructors get called correctly
*/
virtual ~EvalInterface() {};
};
#endif
/**
* @file Token.cpp
*/
#include <sstream>
#include <string>
#include <vector>
#include <stdexcept>
#include "Token.h"
std::string opToString(Operator o) {
std::string result;
switch(o) {
case ADD:
result = "ADD";
break;
case SUBTRACT:
result = "SUBTRACT";
break;
case MULTIPLY:
result = "MULTIPLY";
break;
case DIVIDE:
result = "DIVIDE";
break;
}
return result;
}
std::ostream& operator<<(std::ostream& os, const Token& t) {
std::string type;
switch (t.tag) {
case OPERATOR:
os << "OPERATOR: " << opToString(t.o) << std::endl;
break;
case OPERAND:
os << "OPERAND: " << t.d << std::endl;
break;
case LPAREN:
os << "LPAREN" << std::endl;
break;
case RPAREN:
os << "RPAREN" << std::endl;
break;
default:
throw std::logic_error("Invalid token");
break;
}
return os;
}
std::vector<Token> tokenize(std::string s) {
std::stringstream ss(s);
std::vector<Token> result;
while (ss) {
Token t;
if (ss.peek() == ' ') {
ss.get();
continue;
}
if (isalnum(ss.peek())) {
ss >> t.d;
t.tag = OPERAND;
}
else {
char op;
ss >> op;
t.d = 0;
if (op == '(') {
t.tag = LPAREN;
}
else if (op == ')') {
t.tag = RPAREN;
}
else if (op == '*') {
t.o = MULTIPLY;
t.tag = OPERATOR;
}
else if (op == '/') {
t.o = DIVIDE;
t.tag = OPERATOR;
}
else if (op == '+') {
t.o = ADD;
t.tag = OPERATOR;
}
else if (op == '-') {
t.o = SUBTRACT;
t.tag = OPERATOR;
}
else {
throw std::logic_error("Invalid token");
}
}
result.push_back(t);
}
result.pop_back();
return result;
}
/**
* @file tokenize.cpp
* @brief print the tokenized output of an expression.
*/
#include <iostream>
#include <string>
#include <vector>
#include "Token.h"
/**
* @brief parse a command line string into tokens and print a string
* representation of the tokens.
* @param argc the number of command line arguments
* @param argv the command line argument strings
* @return 0 on successful execution
*/
int main(int argc, char **argv) {
if (argc != 2) {
std::cout << "Usage: " << argv[0] << " \"expression\"" << std::endl;
return -1;
}
std::vector<Token> tokens = tokenize(argv[1]);
for (unsigned int i = 0; i < tokens.size(); i++) {
std::cout << tokens[i];
}
return 0;
}
/**
* @file postfix_calculator.cpp
*/
#include "PostfixCalculator.h"
int main(int argc, char** argv) {
if (argc != 2) {
std::cout << "Usage: " << argv[0] << " \"postfix expression\"" << std::endl;
return -1;
}
std::vector<Token> tokens = tokenize(argv[1]);
PostfixCalculator p;
std::cout << p.eval(tokens) << std::endl;
return 0;
}
CC=g++
#CFLAGS=-Wall -Wextra -std=c++11 -g
CFLAGS=-Wall -Wextra -g
POSTFIX_SOURCES =\
src/PostfixCalculator.cpp\
src/Token.cpp\
src/postfix_calculator.cpp
INFIX_SOURCES =\
src/PostfixCalculator.cpp\
src/Token.cpp\
src/InfixCalculator.cpp\
src/infix_calculator.cpp
TOKENIZE_SOURCES =\
src/Token.cpp\
src/tokenize.cpp
.PHONY: all
all: build/infix_calculator build/postfix_calculator build/tokenize
build/infix_calculator: $(INFIX_SOURCES) | build
$(CC) $(CFLAGS) $(INFIX_SOURCES) -o build/infix_calculator
build/postfix_calculator: $(POSTFIX_SOURCES) | build
$(CC) $(CFLAGS) $(POSTFIX_SOURCES) -o build/postfix_calculator
build/tokenize: $(TOKENIZE_SOURCES) | build
$(CC) $(CFLAGS) $(TOKENIZE_SOURCES) -o build/tokenize
build:
@mkdir -p $@
.PHONY: documentation
documentation: $(SOURCES)
doxygen
.PHONY: test
test: build/infix_calculator build/postfix_calculator build/tokenize
./build/tokenize "2 3 4 + *"
./build/postfix_calculator "2 3 4 + *"
./build/tokenize "2 * (3 + 4)"
./build/infix_calculator "2 * (3 + 4)"
.PHONY: clean
clean:
-rm -rf build
-rm -rf docs
/**
* @file InfixCalculator.cpp
*/
#include <sstream>
#include <cstdlib>
#include <stack>
#include <stdexcept>
#include <string>
#include "InfixCalculator.h"
using namespace std;
int opOrder(Token tok){
switch (tok.o)
{
case ADD : case SUBTRACT : return 1;
case MULTIPLY : case DIVIDE : return 2;
default : return 0;
}
}
std::vector<Token> InfixCalculator::infixToPostfix(std::vector<Token> tokens) {
//TODO: convert infix to postfix
std::stack<Token>s;
std::vector<Token>postfix;
for (unsigned int i = 0; i < tokens.size(); i++){ //for ( each character ch in the infix expression)
switch (tokens[i].tag){ //switch(ch)
case OPERAND: //// Append operand to end of postfix expression—step 1
postfix.push_back(tokens[i]); //postfixExp = postfix * ch
break; //break;
case LPAREN: // Save '(' on stack—step 2
s.push(tokens[i]); // aStack.push(ch)
break; //break;
case OPERATOR: // Process stack operators of greater precedence—step 3
while(!s.empty() && tokens[i].tag != LPAREN && opOrder(tokens[i])<= opOrder(s.top())){
postfix.push_back(s.top()); //Append aStack.peek() to the end of postfixExp
s.pop(); //pop
}
s.push(tokens[i]); //save the operator
break;
case RPAREN:
while(tokens[i].tag != LPAREN){ // Pop stack until matching '(' —step
postfix.push_back(s.top());
s.pop();
}
s.pop(); //remove the open parenthesis
break;
}
}
// Append to postfixExp the operators remaining in the stack—step 5
while (!s.empty()){
postfix.push_back(s.top());
s.pop();
}
return tokens;
}
double InfixCalculator::eval(std::vector<Token> tokens) {
return pc.eval(infixToPostfix(tokens));
}
/**
* @file InfixCalculator.h
*/
#ifndef INFIX_CALCULATOR_H
#define INFIX_CALCULATOR_H
#include<vector>
#include "EvalInterface.h"
#include "PostfixCalculator.h"
class InfixCalculator : public EvalInterface<double>
{
private:
PostfixCalculator pc;
std::vector<Token> infixToPostfix(std::vector<Token> expr);
public:
double eval(std::vector<Token> expr);
};
#endif
/**
* @file infix_calculator.cpp
*/
#include "InfixCalculator.h"
int main(int argc, char** argv) {
if (argc != 2) {
std::cout << "Usage: " << argv[0] << " \"infix expression\"" << std::endl;
return -1;
}
std::vector<Token> tokens = tokenize(argv[1]);
InfixCalculator ic;
std::cout << ic.eval(tokens) << std::endl;
return 0;
}