Skip to content

Instantly share code, notes, and snippets.

@Hornwitser

Hornwitser/calc.cpp

Last active September 4, 2016 03:29
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Hornwitser/c0713580375b2e8fb6a57d70068a0692 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Hornwitser/c0713580375b2e8fb6a57d70068a0692 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Hornwitser revised this gist Sep 4, 2016. 1 changed file with 5 additions and 18 deletions.
    23 changes: 5 additions & 18 deletions calc.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -102,26 +102,13 @@ int parse_number(const std::string& in, StringPos* p_pos)
    {
    StringPos& pos = *p_pos;

    // Before you comment on this, know that the C++ standard does not
    // specify the character set used. Expressions like num = c - '0'
    // assumes that the characters 0-9 is in order and this is not a
    // guarantee provided by the C++ standard.

    int num = 0;
    while (pos < in.size()) {
    char c = in[pos];
    switch (c) {
    case '0': num = num * 10; break;
    case '1': num = num * 10 + 1; break;
    case '2': num = num * 10 + 2; break;
    case '3': num = num * 10 + 3; break;
    case '4': num = num * 10 + 4; break;
    case '5': num = num * 10 + 5; break;
    case '6': num = num * 10 + 6; break;
    case '7': num = num * 10 + 7; break;
    case '8': num = num * 10 + 8; break;
    case '9': num = num * 10 + 9; break;
    default:
    if (c >= '0' && c <= '9') {
    num = num * 10 + c - '0';

    } else {
    pos--; // put the char back in the stream
    return num;
    }
    @@ -433,4 +420,4 @@ int main() {

    std::cout << "= " << result << std::endl;
    }
    }
    }
  2. Hornwitser created this gist Sep 4, 2016.
    436 changes: 436 additions & 0 deletions calc.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,436 @@
    /*
    * 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;

    // Before you comment on this, know that the C++ standard does not
    // specify the character set used. Expressions like num = c - '0'
    // assumes that the characters 0-9 is in order and this is not a
    // guarantee provided by the C++ standard.

    int num = 0;
    while (pos < in.size()) {
    char c = in[pos];
    switch (c) {
    case '0': num = num * 10; break;
    case '1': num = num * 10 + 1; break;
    case '2': num = num * 10 + 2; break;
    case '3': num = num * 10 + 3; break;
    case '4': num = num * 10 + 4; break;
    case '5': num = num * 10 + 5; break;
    case '6': num = num * 10 + 6; break;
    case '7': num = num * 10 + 7; break;
    case '8': num = num * 10 + 8; break;
    case '9': num = num * 10 + 9; break;
    default:
    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;
    }
    }