The Miracle Calculator Development

3 min readMar 22, 2023

Many of us was interviewed at employment. And test tasks so stressful for every person, no exceptions here. Considering high tech industry it is most frequently test task to develop a simple calculator. There is another examples too. Development of calendar can be treated just the same way. But because a computer is a calculation machine predominantly, a simple math calculator will present.

Goal

Required to develop a program for calculation of addition, subtraction, multiplication, division, taking into account precedence of operators and parenthesis. And required high precision of calculations — at least two digits in fraction.

Prerequisites

The solution should be written on C++ programming language with standard library usage. No another dependencies in the project.

Architecture

The kernel compose of:

TokensParser
SyntacticAnalyzer
Executor
Calculator

TokensParser takes expression string as input data and splits it to a sequence of tokens. Tokens abstraction simplify next parsing phase.

SyntacticAnalyzer analyzes the sequence of tokens and builds abstract syntax tree. The rules of building defined in the calculator’s grammar.

Executor performs calculation of abstract syntax tree number value.

Calculator uses and coordinates interaction of all noted modules.

TokensParser

This is a simple service which reads character by character input string and forms a token as returned value.

class TokensParser {
public:
    TokensParser(string source);

    Token getToken();

private:
    stringstream stream;

    map<char, Operator> operators {
        { '+', Operator::plus },
        { '-', Operator::minus },
        { '*', Operator::multiplication },
        { '/', Operator::division }
    };

    map<char, Punctuator> punctuators {
        { '(', Punctuator::left_parenthesis },
        { ')', Punctuator::right_parenthesis }
    };

    char getCharacter();
    double getNumber(char character);
    optional<Operator> getOperator(char character);
    optional<Punctuator> getPunctuator(char character);
};

Because the calculator is a test task program a token set is pretty straightforward.

class Token {
public:
    enum class Kind {
        number,
        _operator,
        punctuator,
        endOfInput,
        unknown
    };

    Token(Kind kind);
    Token(Kind kind, double value);
    Token(Operator op);
    Token(Punctuator punctuator);

    Kind getKind() const;
    double getNumber() const;
    Operator getOperator() const;
    Punctuator getPunctuator() const;

private:
    Kind kind;
    optional<double> number;
    optional<Operator> _operator;
    optional<Punctuator> punctuator;
};

SyntacticAnalyzer

The most important component of the system, because it implements calculator’s grammar. In which case difficulty of the component is high. There is recursion, inheritance and polymorphism used.

class SyntacticAnalyzer {
public:
    SyntacticAnalyzer(TokensParser& tokensParser);

    shared_ptr<Expression> parse();

private:
    using Precedence = int;

    TokensParser& tokensParser;

    shared_ptr<Expression> parseExpression();
    shared_ptr<Expression> parseExpression(Precedence precedence, shared_ptr<Expression> lhs, shared_ptr<BinaryOperator> binaryOperator);
    shared_ptr<Expression> parseUnaryExpression();
    shared_ptr<UnaryOperator> parseUnaryOperator(Token token);
    shared_ptr<BinaryOperator> parseBinaryOperator(Token token);
    shared_ptr<Operand> parseOperand(Token token);
    Precedence getPrecedence(Token token);
    Precedence getPrecedence(Operator op);
    Precedence getPrecedence(Punctuator punctuator);
    Token getToken();
};

As mentioned, the abstract syntax tree uses inheritance, so a base unit of it is a node. The node can reference another same nodes. Because number of nodes is huge, they are not present in the article. A reader can research the project’s source code for details instead.

There is a point. Precedence of operators considered while building the tree. This is the main difference from legacy solution was presented earlier. And this approach is better, because the precedence is defined in source code of program instead the grammar.

Executor

The component, which performs calculation of abstract syntax tree number value. If there is performance requirements, then some sort of optimizations are placed there also. But, as mentioned, the program is a test task, so implementation consists of only pair of simple methods.

class Executor {
public:
    Executor(shared_ptr<Expression> expression);

    double execute();

private:
    shared_ptr<Expression> expression;

    double execute(shared_ptr<Expression> expression);
    double execute(UnaryExpression& unaryExpression);
};

Calculator

The final component, which circuits the kernel’s quartet. For own work it uses all described above components. Adding this abstraction is conditioned by reusabilityand test needs.

class Calculator {
public:
    double calculate(string expression);
};

Conclusion

If look at the origins of programming, then common features can be found for all calculation programs such as simple calculator or more complex compiler. This features include the tokens parser (frequently named as Lex, Lexer, Scanner) and abstract syntax tree parser (frequently named as AST, SyntacticAnalyzer).

Taking a step forward can find a solution usage possibility as frontend level for backend level in which case is the LLVM virtual machine. But this topic is beyond of the scope of the article, so offered for self-research.