Skip to content

Instantly share code, notes, and snippets.

@Hornwitser

Hornwitser/calc.cpp

Last active September 4, 2016 03:29
Show Gist options
  • Save Hornwitser/c0713580375b2e8fb6a57d70068a0692 to your computer and use it in GitHub Desktop.
Save Hornwitser/c0713580375b2e8fb6a57d70068a0692 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
calc.cpp
/*
* Hornwitser's silly calculator app v0.1
*/
#include <vector>
#include <string>
#include <sstream>
#include <stdexcept>
#include <iostream>
struct pass {
template <typename... Ts> pass(Ts&...) {}
};
// useful function for creating a string out of variables
template <typename... Ts>
std::string compose(Ts... parts) {
std::ostringstream result;
pass{result << parts...};
return result.str();
}
struct Token;
typedef std::string::size_type StringPos;
typedef std::vector<Token>::size_type TokenPos;
struct Token {
enum Type {
Number,
Pluss,
Minus,
Multiply,
Divide,
ParenOpen,
ParenClose,
EndOfInput,
} type;
StringPos pos;
int value;
Token(Type type, StringPos pos, int value = 0)
: type(type), pos(pos), value(value)
{}
};
class InputError: public std::runtime_error
{
public:
const StringPos pos;
InputError(std::string what, StringPos pos)
: runtime_error(what), pos(pos)
{}
};
class ParseError: public InputError
{
public:
ParseError(std::string what, StringPos pos)
: InputError(compose("ParseError: ", what), pos)
{}
};
class SyntaxError: public InputError
{
public:
SyntaxError(std::string what, StringPos pos)
: InputError(compose("SyntaxError: ", what), pos)
{}
};
class DivideByZeroError: public InputError
{
public:
DivideByZeroError(std::string what, StringPos pos)
: InputError(compose("DivideByZeroError: ", what), pos)
{}
};
std::ostream& operator<<(std::ostream& os, Token::Type t)
{
switch (t) {
case Token::Number: os << "number"; break;
case Token::Pluss: os << "'+'"; break;
case Token::Minus: os << "'-'"; break;
case Token::Multiply: os << "'*'"; break;
case Token::Divide: os << "'/'"; break;
case Token::ParenOpen: os << "'('"; break;
case Token::ParenClose: os << "')'"; break;
case Token::EndOfInput: os << "end of input"; break;
default: os << "[unkown id " << (int)t << "]"; break;
}
return os;
}
int parse_number(const std::string& in, StringPos* p_pos)
{
StringPos& pos = *p_pos;
int num = 0;
while (pos < in.size()) {
char c = in[pos];
if (c >= '0' && c <= '9') {
num = num * 10 + c - '0';
} else {
pos--; // put the char back in the stream
return num;
}
pos++;
}
pos--; // don't ask..
return num;
}
std::vector<Token> tokenize(const std::string& in)
{
std::vector<Token> tokens;
StringPos pos = 0;
while (pos < in.size()) {
char c = in[pos];
switch (c) {
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
{
auto start_pos = pos;
int num = parse_number(in, &pos);
tokens.emplace_back(Token::Number, start_pos, num);
break;
}
case '+':
tokens.emplace_back(Token::Pluss, pos);
break;
case '-':
tokens.emplace_back(Token::Minus, pos);
break;
case '*':
tokens.emplace_back(Token::Multiply, pos);
break;
case '/':
tokens.emplace_back(Token::Divide, pos);
break;
case '(':
tokens.emplace_back(Token::ParenOpen, pos);
break;
case ')':
tokens.emplace_back(Token::ParenClose, pos);
break;
case ' ':
case '\t':
break; // ignore whitespace
default:
throw ParseError(compose("Unknown character '", c, "'"), pos);
}
pos++;
}
tokens.emplace_back(Token::EndOfInput, pos);
return tokens;
}
/* The following code is a manually put together parser of the language
* expressed bellow in BNF.
*
* <experssion> ::= <add-expr> [end of input]
* <add-expr> ::= <add-expr> '+' <mul-expr>
* | <add-expr> '-' <mul-expr>
* | <mul-expr>
* <mul-expr> ::= <mul-expr> '*' <paren-expr>
* | <mul-expr> '/' <paren-expr>
* | <paren-expr>
* <paren-expr> ::= '(' <add-expr> ')'
* | <unary-expr>
* <unary-expr> ::= '-' <number>
* | <number>
*/
int unary_expr(const std::vector<Token>& tokens, TokenPos* p_pos)
{
TokenPos& pos = *p_pos;
Token t = tokens[pos];
switch (t.type) {
case Token::Number:
pos++;
return t.value;
case Token::Minus:
pos++;
t = tokens[pos];
if (t.type == Token::Number) {
pos++;
return -t.value;
} else {
throw SyntaxError(
compose("Expected number but got ", t.type),
t.pos
);
}
case Token::ParenOpen:
case Token::Pluss:
case Token::Multiply:
case Token::Divide:
case Token::ParenClose:
case Token::EndOfInput:
default:
throw SyntaxError(
compose("Expected '-' or number but got ", t.type),
t.pos
);
}
}
int add_expr(const std::vector<Token>& tokens, TokenPos* p_pos);
int paren_expr(const std::vector<Token>& tokens, TokenPos* p_pos)
{
TokenPos& pos = *p_pos;
Token t = tokens[pos];
switch (t.type) {
case Token::Number:
case Token::Minus:
return unary_expr(tokens, &pos);
break;
case Token::ParenOpen:
{
pos++;
int result = add_expr(tokens, &pos);
t = tokens[pos];
if (t.type == Token::ParenClose) {
pos++;
return result;
} else {
throw SyntaxError(
compose("Expected ')' but got ", t.type),
t.pos
);
}
break;
}
case Token::Pluss:
case Token::Multiply:
case Token::Divide:
case Token::ParenClose:
case Token::EndOfInput:
default:
throw SyntaxError(
compose("Expected number, '-' or '(', but got ", t.type),
t.pos
);
}
}
int mul_expr(const std::vector<Token>& tokens, TokenPos* p_pos)
{
TokenPos& pos = *p_pos;
int lhs = paren_expr(tokens, &pos);
while (true) {
Token t = tokens[pos];
switch (t.type) {
case Token::Multiply:
pos++;
lhs *= paren_expr(tokens, &pos);
break;
case Token::Divide:
{
pos++;
int rhs = paren_expr(tokens, &pos);
if (rhs == 0) {
throw DivideByZeroError("Divide by zero", t.pos);
}
lhs /= rhs;
break;
}
case Token::Number:
case Token::ParenOpen:
throw SyntaxError(
compose(
"Expected '+', '-', '*', '/' or end of input but got ",
t.type
),
t.pos
);
case Token::Minus:
case Token::Pluss:
case Token::ParenClose:
case Token::EndOfInput:
default:
return lhs;
}
}
}
int add_expr(const std::vector<Token>& tokens, TokenPos* p_pos)
{
TokenPos& pos = *p_pos;
int lhs = mul_expr(tokens, &pos);
while (true) {
Token t = tokens[pos];
switch (t.type) {
case Token::Pluss:
pos++;
lhs += mul_expr(tokens, &pos);
break;
case Token::Minus:
pos++;
lhs -= mul_expr(tokens, &pos);
break;
case Token::Number:
case Token::ParenOpen:
case Token::Multiply:
case Token::Divide:
throw SyntaxError(
compose(
"This cannot possibly happen, how did you get ", t.type,
" to trigger this?!?"),
t.pos
);
case Token::ParenClose:
case Token::EndOfInput:
default:
return lhs;
}
}
}
int expression(const std::vector<Token>& tokens)
{
TokenPos pos = 0;
int value = add_expr(tokens, &pos);
Token t = tokens[pos];
if (t.type == Token::EndOfInput) {
return value;
} else {
throw SyntaxError(
compose("Expected end of input but got ", t.type),
t.pos
);
}
}
int main() {
std::cout << "=== Hornwitser's silly calculator app v0.1 ===\n"
"\n"
"Supported operands are + - * / ( ) and unary -\n"
"Exit with \"quit\" or \"exit\".\n"
"\n";
while (true) {
std::cout << "> ";
std::string input;
std::getline(std::cin, input);
if (input == "quit" || input == "exit")
break;
std::vector<Token> tokens;
try {
tokens = tokenize(input);
} catch (InputError e) {
std::cout << std::string(e.pos+2, ' ') << "^\n";
std::cout << e.what() << std::endl;
continue;
}
if (tokens[0].type == Token::EndOfInput)
continue;
int result;
try {
result = expression(tokens);
} catch (InputError e) {
std::cout << std::string(e.pos+2, ' ') << "^\n";
std::cout << e.what() << std::endl;
continue;
}
std::cout << "= " << result << std::endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment