Last active
December 26, 2021 20:12
-
-
Save r4nx/3f22fd4137297cdd8199140e09bcc9c7 to your computer and use it in GitHub Desktop.
Parsing-based calculator in C++20
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cctype> | |
| #include <cmath> | |
| #include <cstdint> | |
| #include <iostream> | |
| #include <map> | |
| #include <stack> | |
| #include <stdexcept> | |
| #include <string> | |
| #include <string_view> | |
| #include <utility> | |
| #include <variant> | |
| #include <vector> | |
| // In order of increasing precedence | |
| enum class Token : uint8_t { | |
| num, | |
| add, | |
| sub, | |
| mul, | |
| div, | |
| mod, | |
| pow, | |
| parent_left, | |
| parent_right | |
| }; | |
| const std::map<Token, uint8_t> precedence_table{ | |
| {Token::add, 1}, | |
| {Token::sub, 1}, | |
| {Token::mul, 2}, | |
| {Token::div, 2}, | |
| {Token::mod, 2}, | |
| {Token::pow, 3}}; | |
| // Operand type | |
| using op_t = long long; | |
| using token_t = std::pair<Token, std::variant<std::monostate, op_t>>; | |
| std::vector<token_t> get_tokens(std::string_view input) | |
| { | |
| std::vector<token_t> tokens; | |
| Token mc_token = Token::num; // mc stands for "multicharacter" | |
| // Buffer to store the tokens consisting of multiple characters | |
| std::string buf; | |
| auto flush_buf = [&buf, &mc_token, &tokens] { | |
| if (buf.size() > 0) | |
| { | |
| tokens.emplace_back(mc_token, std::stoi(buf)); | |
| buf.clear(); | |
| } | |
| }; | |
| for (auto c : input) | |
| { | |
| Token token = Token::num; | |
| switch (c) | |
| { | |
| case '+': | |
| token = Token::add; | |
| break; | |
| case '-': | |
| token = Token::sub; | |
| break; | |
| case '*': | |
| token = Token::mul; | |
| break; | |
| case '/': | |
| token = Token::div; | |
| break; | |
| case '%': | |
| token = Token::mod; | |
| break; | |
| case '^': | |
| token = Token::pow; | |
| break; | |
| case '(': | |
| token = Token::parent_left; | |
| break; | |
| case ')': | |
| token = Token::parent_right; | |
| break; | |
| default: | |
| if (std::isdigit(c)) | |
| { | |
| mc_token = Token::num; | |
| buf.push_back(c); | |
| } | |
| continue; | |
| } | |
| flush_buf(); | |
| tokens.emplace_back(token, std::monostate{}); | |
| } | |
| // One more time for the case when there is a number | |
| // right in the end of input | |
| flush_buf(); | |
| return tokens; | |
| } | |
| double execute_operator(Token op, double a, double b) | |
| { | |
| auto mod = [](double x, op_t y) { | |
| return x - static_cast<op_t>(x / y) * y; | |
| }; | |
| switch (op) | |
| { | |
| case Token::add: | |
| return a + b; | |
| case Token::sub: | |
| return a - b; | |
| case Token::mul: | |
| return a * b; | |
| case Token::div: | |
| return a / b; | |
| case Token::mod: | |
| return mod(a, static_cast<op_t>(b)); | |
| case Token::pow: | |
| return std::pow(a, b); | |
| default: | |
| return 0; | |
| } | |
| } | |
| auto get_precedence(Token token) | |
| { | |
| // Consequences would be sad enough if it can't find the token in the map | |
| // (dereferencing the off-the-end iterator actually), but it's filled | |
| // manually in the code so it shouldn't happen (at least I hope) | |
| return precedence_table.find(token)->second; | |
| } | |
| double parse(const std::vector<token_t> &tokens) | |
| { | |
| std::stack<double> operands; | |
| std::stack<Token> operators; | |
| auto pop_operator = [&operands, &operators] { | |
| const auto op = operators.top(); | |
| operators.pop(); | |
| // We have only one unary operator so the condition is quite | |
| // simple | |
| const bool binary = true; // op != Token::sub; | |
| const auto b = binary ? operands.top() : 0; | |
| if (binary) | |
| operands.pop(); | |
| const auto a = operands.top(); | |
| operands.pop(); | |
| operands.push(execute_operator(op, a, b)); | |
| }; | |
| for (const auto &token : tokens) | |
| { | |
| const auto &[token_id, data] = token; | |
| switch (token_id) | |
| { | |
| case Token::num: | |
| operands.push(std::get<op_t>(data)); | |
| break; | |
| case Token::parent_left: | |
| operators.push(token_id); | |
| break; | |
| case Token::parent_right: | |
| while (!operators.empty() | |
| && operators.top() != Token::parent_left) | |
| { | |
| pop_operator(); | |
| } | |
| // Stack ran out without finding a left parenthesis | |
| if (operators.empty()) | |
| throw std::logic_error{"Mismatched parenthesis"}; | |
| else | |
| operators.pop(); | |
| break; | |
| default: | |
| while (!operators.empty() | |
| && operators.top() != Token::parent_left | |
| && get_precedence(token_id) | |
| <= get_precedence(operators.top())) | |
| { | |
| pop_operator(); | |
| } | |
| operators.push(token_id); | |
| break; | |
| } | |
| } | |
| // Process the remaining operators | |
| while (!operators.empty()) | |
| pop_operator(); | |
| return operands.top(); | |
| } | |
| int main() | |
| { | |
| std::string input; | |
| std::cout << "Expression: "; | |
| std::getline(std::cin, input); | |
| auto result = parse(get_tokens(input)); | |
| std::cout << std::endl << "Result: " << result << std::endl; | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment