4
\$\begingroup\$

As a coding exercise, I am trying to implement a calculator which takes string as input, with addition (+), subtraction (-), multiplication (*), division (/) and power (^) functions. For example, given input string "-12.3456 + 2 ^ 3 * 3.123" to a function, it can output double result "12.6384".

The experimental implementation

  • StringCalculator class implementation

    class StringCalculator
    {
        public:           
            StringCalculator(const std::string& input)
            {
                //  remove spaces
                auto input_without_space = remove_spaces(input);
                parser(input_without_space);
    
                while(operators.size() > 0)
                {
                    perform_computing();
                }
    
            }
    
            long double get_result()
            {
                return numbers[0];
            }
        private:
            std::vector<long double> numbers;
            std::vector<std::string> operators;
    
            constexpr void parser(std::string_view input_string)
            {
                int floating_point_count = 0;
                long double single_number = 0;
                bool floating_point = false;
                for(std::size_t index = 0; index < input_string.size(); ++index)
                {
                    if(std::isdigit(input_string[index]) || input_string[index] == '.')
                    {
                        if(input_string[index] != '.')
                        {
                            if(floating_point == false)
                            {
                                single_number = single_number * 10 + (static_cast<int>(input_string[index]) - 48);
                            }
                            else
                            {
                                floating_point_count = floating_point_count + 1;
                                single_number = single_number + (static_cast<int>(input_string[index]) - 48) / std::pow(10, floating_point_count);
                            }
                        }
                        else
                        {
                            if(floating_point)
                                throw std::runtime_error("Float-point parsing error!");
                            else
                                floating_point = true;
                        }
                    }
                    else
                    {
                        if( input_string[index] == '+' ||
                            input_string[index] == '-' ||
                            input_string[index] == '*' ||
                            input_string[index] == '/' ||
                            input_string[index] == '^')
                        {
                            operators.push_back(std::string{input_string[index]});
                            numbers.push_back(single_number);
                            single_number = 0;
                            floating_point = false;
                            floating_point_count = 0;
                        }
    
    
    
                    }
                }
                numbers.push_back(single_number);
            }
    
            constexpr void perform_computing()
            {
                //  level 1 computation: ^ (power)
                for(std::size_t index = 0; index < operators.size(); ++index)
                {
                    if(operators[index] == "^")
                    {
                        numbers[index] = std::pow(numbers[index], numbers[index + 1]);
                        reduce_operators_and_numbers(index);
                    }
                }
                //  level 2 computation: * (multiplication) and / (division)
                for(std::size_t index = 0; index < operators.size(); ++index)
                {
                    if(operators[index] == "*")
                    {
                        numbers[index] = numbers[index] * numbers[index + 1];
                        reduce_operators_and_numbers(index);
                    }
                    if(operators[index] == "/")
                    {
                        numbers[index] = numbers[index] / numbers[index + 1];
                        reduce_operators_and_numbers(index);
                    }
                }
                //  level 3 computation: + (addition) and - (subtraction)
                for(std::size_t index = 0; index < operators.size(); ++index)
                {
                    if(operators[index] == "+")
                    {
                        numbers[index] = numbers[index] + numbers[index + 1];
                        reduce_operators_and_numbers(index);
                    }
                    if(operators[index] == "-")
                    {
                        numbers[index] = numbers[index] - numbers[index + 1];
                        reduce_operators_and_numbers(index);
                    }
                }
            }
    
            constexpr void reduce_operators_and_numbers(std::size_t index)
            {
                for(std::size_t index1 = index; index1 < operators.size() - 1; ++index1)
                {
                    operators[index1] = operators[index1 + 1];
                }
                operators.resize(operators.size() - 1);
                for(std::size_t index1 = index; index1 < numbers.size() - 2; ++index1)
                {
                    numbers[index1 + 1] = numbers[index1 + 2];
                }
                numbers.resize(numbers.size() - 1);
            }
    
            //  copy from https://stackoverflow.com/a/83481/6667035
            std::string remove_spaces(std::string str) 
            {
                std::string::iterator end_pos = std::remove(str.begin(), str.end(), ' ');
                str.erase(end_pos, str.end());
                return str;
            }
    };
    

Full Testing Code

The full testing code:

//  String Calculator in C++

#include <algorithm>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <concepts>
#include <execution>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <ranges>
#include <stack>
#include <string>

//  From https://stackoverflow.com/a/37264642/6667035
#ifndef NDEBUG
#   define M_Assert(Expr, Msg) \
    M_Assert_Helper(#Expr, Expr, __FILE__, __LINE__, Msg)
#else
#   define M_Assert(Expr, Msg) ;
#endif

void M_Assert_Helper(const char* expr_str, bool expr, const char* file, int line, const char* msg)
{
    if (!expr)
    {
        std::cerr << "Assert failed:\t" << msg << "\n"
            << "Expected:\t" << expr_str << "\n"
            << "Source:\t\t" << file << ", line " << line << "\n";
        abort();
    }
}

class StringCalculator
{
    public:           
        StringCalculator(const std::string& input)
        {
            //  remove spaces
            auto input_without_space = remove_spaces(input);
            parser(input_without_space);
            
            while(operators.size() > 0)
            {
                perform_computing();
            }
            
        }

        long double get_result()
        {
            return numbers[0];
        }
    private:
        std::vector<long double> numbers;
        std::vector<std::string> operators;

        constexpr void parser(std::string_view input_string)
        {
            int floating_point_count = 0;
            long double single_number = 0;
            bool floating_point = false;
            for(std::size_t index = 0; index < input_string.size(); ++index)
            {
                if(std::isdigit(input_string[index]) || input_string[index] == '.')
                {
                    if(input_string[index] != '.')
                    {
                        if(floating_point == false)
                        {
                            single_number = single_number * 10 + (static_cast<int>(input_string[index]) - 48);
                        }
                        else
                        {
                            floating_point_count = floating_point_count + 1;
                            single_number = single_number + (static_cast<int>(input_string[index]) - 48) / std::pow(10, floating_point_count);
                        }
                    }
                    else
                    {
                        if(floating_point)
                            throw std::runtime_error("Float-point parsing error!");
                        else
                            floating_point = true;
                    }
                }
                else
                {
                    if( input_string[index] == '+' ||
                        input_string[index] == '-' ||
                        input_string[index] == '*' ||
                        input_string[index] == '/' ||
                        input_string[index] == '^')
                    {
                        operators.push_back(std::string{input_string[index]});
                        numbers.push_back(single_number);
                        single_number = 0;
                        floating_point = false;
                        floating_point_count = 0;
                    }
                        
                    
                    
                }
            }
            numbers.push_back(single_number);
        }

        constexpr void perform_computing()
        {
            //  level 1 computation: ^ (power)
            for(std::size_t index = 0; index < operators.size(); ++index)
            {
                if(operators[index] == "^")
                {
                    numbers[index] = std::pow(numbers[index], numbers[index + 1]);
                    reduce_operators_and_numbers(index);
                }
            }
            //  level 2 computation: * (multiplication) and / (division)
            for(std::size_t index = 0; index < operators.size(); ++index)
            {
                if(operators[index] == "*")
                {
                    numbers[index] = numbers[index] * numbers[index + 1];
                    reduce_operators_and_numbers(index);
                }
                if(operators[index] == "/")
                {
                    numbers[index] = numbers[index] / numbers[index + 1];
                    reduce_operators_and_numbers(index);
                }
            }
            //  level 3 computation: + (addition) and - (subtraction)
            for(std::size_t index = 0; index < operators.size(); ++index)
            {
                if(operators[index] == "+")
                {
                    numbers[index] = numbers[index] + numbers[index + 1];
                    reduce_operators_and_numbers(index);
                }
                if(operators[index] == "-")
                {
                    numbers[index] = numbers[index] - numbers[index + 1];
                    reduce_operators_and_numbers(index);
                }
            }
        }

        constexpr void reduce_operators_and_numbers(std::size_t index)
        {
            for(std::size_t index1 = index; index1 < operators.size() - 1; ++index1)
            {
                operators[index1] = operators[index1 + 1];
            }
            operators.resize(operators.size() - 1);
            for(std::size_t index1 = index; index1 < numbers.size() - 2; ++index1)
            {
                numbers[index1 + 1] = numbers[index1 + 2];
            }
            numbers.resize(numbers.size() - 1);
        }

        //  copy from https://stackoverflow.com/a/83481/6667035
        std::string remove_spaces(std::string str) 
        {
            std::string::iterator end_pos = std::remove(str.begin(), str.end(), ' ');
            str.erase(end_pos, str.end());
            return str;
        }
};

//  Copy from: https://stackoverflow.com/a/37686/6667035
constexpr bool AreSame(double a, double b) {
    return std::fabs(a - b) < std::numeric_limits<double>::epsilon();
}

int main()
{
    auto start = std::chrono::system_clock::now();
    StringCalculator sc1("-12.3456 + 2 ^ 3 * 3.123");
    M_Assert(
        AreSame(sc1.get_result(), 12.6384),
        "\"-12.3456 + 2 ^ 3 * 3.123\" test case failed");
    
    StringCalculator sc2("-0.12345 * 3 - 5");
    M_Assert(
        AreSame(sc2.get_result(), -5.37035),
        "\"-0.12345 * 3 - 5\" test case failed");
    
    StringCalculator sc3("1024*2+2048*4");
    M_Assert(
        AreSame(sc3.get_result(), 10240),
        "\"1024*2+2048*4\" test case failed");

    StringCalculator sc4("10-2*3+2*2-7");
    M_Assert(
        AreSame(sc4.get_result(), 1),
        "\"10-2*3+2*2-7\" test case failed");
    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::time_t end_time = std::chrono::system_clock::to_time_t(end);
    std::cout << "Computation finished at " << std::ctime(&end_time) << "elapsed time: " << elapsed_seconds.count() << '\n';
    return 0;
}

The output of the test code above:

Computation finished at Sat May  4 12:48:52 2024
elapsed time: 1.0409e-05

Godbolt link is here.

All suggestions are welcome.

\$\endgroup\$
1
  • \$\begingroup\$ I really don't speak c++, but "compute in constructor and then return the result from method call" approach looks strange to me - I'd probably drop a class altogether and make this a lone function in namespace. Also using . as a decimal separator might be not the most accessible - some people around the globe really use commas for decimal and dots - for thousands. You can get the default separator from locale. \$\endgroup\$ Commented May 4 at 21:06

2 Answers 2

5
\$\begingroup\$

A few suggestions (got too long for a comment):

  • don't do the calculation in the constructor, but only when the result is needed (lazily)
  • Do you need a separate method to remove leading and trailing spaces? The parser should already handle spaces
  • don't use your own number parsing; instead, find the next delimiter symbol (space or operator), and parse the string before that using std::stold (also checking that the parsed number equal the string length); this makes it less error-prone and takes care of locale handling (there are other possibilities for parsing a number, just use a standard one)
  • naming: "parser" suggests a returned object, use "parse" instead
  • don't use value == false with a Boolean value, use !value instead
  • make it a habit to use emplace_back instead of push_back if possible
  • tests: you are missing tests for incorrect input and edge cases
\$\endgroup\$
4
\$\begingroup\$

Bug in processing:

Power expressions are processed from left to right.

2^3^2

This should be processed as:

2^(3^2)

Your code will do it the wrong way:

(2^3)^2

But the fix is simple:

for(std::size_t index = 0; index < operators.size(); ++index)

Just do this backwards:

for(std::size_t rIndex = operators.size(); rIndex > 0; --rIndex) {
    std::size_t index = rIndex - 1;

Lexing and parsing are basically solved problems.
Use an appropriate tool.

The definition of lexemes and grammers are all over the web pick one up and edit out the expression you need.

Problems:

  • You don't support numbers very well.
    You support the basic definition of a number but most people expect more.
  • Any non trivial expression can not be expressed here.
    You don't support braces () which means any non trivial expression really can not be expressed easily.

Would be nice to support variables and assignments to get around the braces support problem.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ In regard to order of evaluation there is no common standard for Serial exponentiation when using "^" \$\endgroup\$
    – Blindman67
    Commented May 6 at 14:06
  • \$\begingroup\$ @Blindman67 In mathematics, there is a definition. A "Power Tower" is to be evaluated top down. The "^" notation may be clunky way to represent it, but that is supposed to be how it is represented. This is how Wolfram Alpha Interprets it. \$\endgroup\$ Commented May 6 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.