Miracle calculator development
Many of us have gone through job interviews. And they know firsthand how stressful tests are for a candidate before being hired. If we talk about the high-tech sector, then the most frequent test task when interviewing for a developer position is programming calculator. There are other options, such as development calendarbut since the computer is mainly intended for solving computational problems, the implementation of the simplest calculator that supports basic mathematical operations will be considered below.
Task
It is required to develop a program that calculates the values of the operations of addition, subtraction, multiplication and division, while taking into account operation priorities and brackets. You also need to provide high precision calculations, up to two decimal places.
Requirements
The solution must be implemented using the C++ language and the standard library. No additional dependencies can be included in the project.
Architecture
The core of the program will consist of the following components
TokensParser
SyntacticAnalyzer
Executor
calculator
TokensParser takes as input a string containing an expression to be evaluated. Then it parses this expression into components – the so-called tokens. The use of tokens simplifies further parsing of the expression.
SyntacticAnalyzer performs an analysis of the tokens received at the previous stage and, based on them, builds abstract syntax tree expressions. The rules by which an abstract syntax tree is compiled are defined in the grammar of the language.
Executor performs the calculation values abstract syntax tree.
Calculator combines and coordinates the work of all the above modules.
TokensParser
A rather trivial service that reads the original line of text character by character in order to determine which token to generate as a result.
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);
};Since the calculator being developed is only a test task, the set of tokens is limited to several options.
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, since it implements the calculator’s grammar. For this reason, the complexity of the service is somewhat higher than that of all the others, since the technique is applied here. recursiveprogramming, inheritance and polymorphism.
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 already mentioned, the abstract syntax tree is implemented using inheritance, so the basic component of the tree is a node that can hold a reference to similar nodes. Since the number of nodes is large, they will not be presented in this article. Instead, the reader is invited to view the source code of the project for a detailed study.
It is worth noting that here, when compiling a tree, the priorities of operations are also taken into account. This main differencewhich distinguishes this solution from the presented previouslysince the priority of operations is defined in the source code of the program, but not in the grammar of the calculator.
Executor
The component that performs the evaluation of the abstract syntax tree. If any performance requirements are imposed on the program, then at this stage optimization computing. However, as already mentioned, the task is a test one, so the service implementation includes only a couple of the simplest 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 that closes the quadruple, which is the core of the system. For its work, it requires all of the previously listed services. Its introduction is due to the need to test the entire solution, as well as reuse at any point in the program.
class Calculator {
public:
double calculate(string expression);
};Conclusion
Returning to the origins of programming, one can trace the common features that are characteristic of the implementation of computational programs, whether it is a conventional calculator or a more complex compiler. These traits can be described as having a token parser (often called Lex, Lexer, Scanner) and an abstract syntax tree parser (often called AST, SyntacticAnalyzer).
Taking a step forward, we can point out the possibility of using the proposed solution as front end level for the backend level, which is the virtual machine LLVM. But such material is beyond the scope of the article and is offered for independent study.
