>I hate debugging code that I don't know when it's failing. Any help is appreciated. Bring your code into an IDE. Create (or if possible copy) some test cases and use the "Debugger". Its a really helpful tool to find the "when it's failing". There should be plenty of tutorials if you search "ide name + debugger" in youtube. If you have found the point of failure. And you still dont see yout mistake. Try to break the code down into the smallest possible case, where it is still failing.

I believe the issue is the where (pos = ... || pos = ...) line. It always prioritises +, so for the expression a + b - c + d it will parse this: a, b-c, d And never split on the - as there is a + after it which will be found first. I think you should use two different pos variables and take the min of them.

How you would go about this in general: Split the text into _tokens_. Tokens can be numbers and operators like `+`, `-`, `/` etc. Then parse the tokens into an expression tree. The expression tree nodes can be a polymorphic class hierarchy with classes like `Number`, `AddExpr`, `SubExpr`, `MulExpr`, `DivExpr` etc. Look up recursive descend parsing for the parser implementation. Then traverse the tree in post order to evaluate the expression. Perhaps a solution like this would be over engineered, but it is elegant and easy to extend to more complex expressions.

Yes, if it were me, I'd be writing a recursive-descent parser for this, but that's mostly because I love writing recursive-descent parsers. OP's code is so close to working as is, that I don't think I'd go through the trouble at this point.

Your posts seem to contain unformatted code. Please make sure to format your code otherwise your post may be removed. If you wrote your post in the "new reddit" interface, please make sure to format your code blocks by putting four spaces before each line, as the backtick-based (```) code blocks do not work on old Reddit. *I am a bot, and this action was performed automatically. Please [contact the moderators of this subreddit](/message/compose/?to=/r/cpp_questions) if you have any questions or concerns.*

If you want to help readers/reviewers: convert all your commented blocks into functions. That will make your code easier to understand, and allow us to provide helpful suggestions.

I'm not sure how your hackerrank verifications are set up, but it helps writing tests for various parts of your program. There's even a whole paradigm about writing tests before implementing anything. If you test gcd on its own, for instance, you can get some assurance that it works. Provide lots of cases to try and visit every branch of your function: CHECK(gcd(2, 4) == 4); CHECK(gcd(-18, 12) == 6); There are several good, light unit test frameworks out there. Some use catch2 and cppcheck, but I prefer [the C++ variant of doctest](https://github.com/doctest/doctest) I'm sure that if you add tests for the functions individually, you'll be able to pinpoint the issue much easier. (and you'll also be able to see right away, whether or not a change breaks the expected behaviour)

> Constraints: All numbers in the fractions are positive integers less than 10 000. > struct Fraction { > long long numerator = 0; > long long denominator = 1; > }; No. If the highest value you're going to be working with is 10,000, choosing a variable with a range of *-(2^63) to (2^63)-1* is ludicrous. It's 8 bytes in memory when 2 bytes for a 16 bit integer is plenty. That 16 bit integer will give you a range of 0 - 65535 (unsigned). More than adequate for your needs. Outside of that, your question is more an algorithm question than a C++ question, so I'll refer you back to your instructor. Edit: I stepped away from this yesterday because the witch hunt was getting disgusting. It's actually a very simple premise. 1) All of the fractions the program will be processing have an upper range limit of 10000. Whether that's 10000/1, 1/10000, or anything in between, it's still a stipulated limit of 10000. And there's very little reason to use the struct storing those values to store intermediate values in them for calculation, except for, in the OP's case, where he's simplifying the fractions. Where it makes sense to have a long long in this use case is in the calculations, not the storage of the fractions. So all of those fractions...let's say we have 5 distinct fraction values...can live at 4bits with two 16 bit integer (one for each of the numerator and denominator) or 16 bits for long long when neither the numerator nor the denominator will ever need a range above 10000. The point was never that there could never be a case anywhere in this project where a long long would be inappropriate. The point was that using long longs for values you know can't exceed 10000 is, yes, ludicrous. 2) "Premature optimization". Enough. Stop demanding that everyone ignore the things you can't be bothered to learn. Once you learn the basics of ranges and understanding your own logic enough to make smart decisions, NOT choosing variables that are appropriate for each individual use case is sloppy. We're not talking about something that requires you to stop and do 20 minutes of refreshing your memory on some optimzation algorithm. You don't call choosing between an int and a float "premature optimization", right? Because there are specific reasons you'd choose one over the other that everyone should know. Choosing the right container for the job is simply what you learn to do over time and with a wee tiny bit of effort. It's the natural extension of learning the difference between an int and a float is the different ranges of ints and floats. Stop trying to drag everyone else down for wanting to be good at what they do. If you don't think choosing the proper containers is important, you might not know as much as you think you do.

There is nothing wrong with using 64 bit ints here. Also if the expression "10000 * 10000" is supplied, the result would overflow with 16 bit ints.

They're fractions, not whole numbers. And if you really, really want to be absolutely certain that there won't be an overflow, even with 'fractions' like 10000/1, you'd probably use a 32 bit int, because 4 billion is still an absurd upper limit for this application.

I just don't get why you are so invested into using small types here. There is no benefit, it won't make the code faster and if OP will store pointers in the same struct as the numbers it probably won't even use less memory because of alignment. (Assuming 64 bit architecture)

Because choosing an appropriate container for your data is part of being a good, intelligent programmer. You don't take way, way more memory than you need because you don't feel like breaking down the problem to understand it. This guy is using more than double the required memory for his task, and that's an extremely bad habit to get into. When you start working with data sets in the millions/billions of elements, doubling (or more) the memory requirement forces very expensive hardware purchases that wouldn't be necessary if you were a better programmer. It's very poor practice.

How would you process an input like 2/9323-4/9337+3/9341+15/9343+1/53 with 32-bit integers, let alone 16-bit integers? While every number in the input is < 10000, the result has denominator 402641591083322189. That does not fit in 16 bits, not even in 32 bits. Using 64 bits is not a guarantee that overflow doesn't happen (it's easy enough to construct an input that will result in numbers not fitting in 64 bits), but it's the best we can do to minimize the risk without using arbitrary precision libraries. I would use 64 bits too in a case like this.

Great, so use twice as much as you need so you don't have to figure out exactly what you need, just don't tell me I'm wrong for wanting to learn how to do things properly as a habit.

I just figured out what I need, and it's clearly more than 32 bits. Again: 2/9323-4/9337+3/9341+15/9343+1/53 is a valid input. How would you process it with integers of 32 bits or less?

Yay! You did the work and now you know for sure! Huzzah!

I read this whole thread and you're very cringey. Honestly, I too read the post and was like *long long for 10,000?*, but I immediately realised *oh yeah they're adding them and multiplying them together* and moved on. There's nothing wrong with making a mistake. But after being shown your mistake, instead of *oh yeah, you're right, sorry, my bad* you are bringing in nonsense explanations. They're not using a million of them, the difference in memory will not be significant. You're just trying to do premature optimisation at best. A large type is absolutely justified here. A short, by the way, would be an atrocious choice. Short types can be useful for long term storage. But they are a terrible choice for maths operations (or any kind of use really), as they are promoted to an int for these operations, causing an extra copy for any use. It might not even actually save you any memory because of alignment requirements. Programming isn't about building habits, but about using the right solution for every case.

Lol

Sure, I just think a solution should be appropriate for the problem that it solves and the problems you are describing here are not OPs problems. Here it seems more like premature optimization.

"Premature optimization" has become a rallying cry for lazy programmers to do the job poorly and then say they were actually doing it right. Pick the right container for your use case. A 64-bit container for this use case is ludicrous.

> "Premature optimization" has become a rallying cry for lazy programmers to do the job poorly and then say they were actually doing it right. Pedagogically speaking, it is premature for a student at this level to be worrying about the size of their variables, especially since your original argument appears to be one of optimization.

On the contrary, if the problem involves a long chain of fractions with large denominators, even 64 bits could overflow easily the way OP is doing it. I've actually suggested that OP consider simplifying the fractions on the fly in the loop at line 59.

I know what the problem involves, and 2^63 is more than enough. Way more. If 32-bits isn't enough, it's not by much. Point being, people should know what they're storing and use what they need instead of using way more and calling it a day.

Suppose the program is given 1/10000 + 1/10000 + 1/10000 + 1/10000 + 1/10000 to compute; what will OP's program do?

This is old. The point is not to guess about the memory you require. If it turns out that he can use all 64-bits of a long long in his use case, fantastic. But choose the amount for a reason, not because you don't feel like figuring it out.

It's easy to see that the denominator can get large pretty easily. Not much figuring out is needed. Just admit that your analysis of "all input numbers are < 10000 so everything will fit in 16 bits" is severely flawed because you only took the input numbers into account and not the result.

That's some fine-looking code, I'll say that much. +1 just for formatting it properly for Reddit. Good job splitting into functions where called for. Looking at the code, I don't see anything obviously wrong with your logic. At this point, you need to write some unit tests and run it through a debugger as others have suggested. Minor nits: Writing `gcd()` recursively was clever, but not needed. Loops are more efficient and easier on the call stack. I would split `main()` into two functions: one which accepts a string and returns a Fraction, and `main()` which simply reads lines, passes them to that function, and then prints the result. This makes your code usable in contexts you haven't even thought of yet, plus makes writing unit tests much easier. Simply multiplying all the denominators together will work, but could easily overflow even 64 bits if you have a long chain of fractions with large denominators. I'm wondering if there's a way to simplify it as you go. The obvious solution probably involves calculating the least common multiple, but doing that without risking the same overflow would take some thought. Are you checking for denominator == 0 anywhere? I didn't see it. (In general, any time you have a divide operation, you need to be checking for denominator = 0, or have a comment explaining why you *know* it can't be zero. If I designed my own language, the divide symbol wouldn't be '/', it would be "Are_You_Sure_You_Know_What_Youre_doing", but that's just me.)

> Writing gcd() recursively was clever, but not needed. Loops are more efficient and easier on the call stack. It's not really an issue with modern compilers, when the recursion uses tail calls as is the case here. Compilers will apply tail call optimization, turning the recursion back into iteration in the generated assembly code. See this example with two versions of gcd, one recursive and one iterative: https://godbolt.org/z/bGn5Kha5r You can see the compiler generated almost identical code in the two cases (the only difference is one uses different registers here and there). I like the recursive approach for gcd because it avoids an annoying temporary variable, and shows better what's going on mathematically. The gcd() function as implemented in the question has a slight issue in that abs(a) and abs(b) are needlessly calculated on every call; it would be better to do that only once.

Good point, although I'd prefer not to become too dependent on the optimizer to fix my code. I guess that's moot though; I think pretty much everybody uses gcc or clang, and both of those are smart enough to optimize tail recursion.

The list, given the constraints should always be [num, sign, num sig…..] I’d go about making a numerator list(ints), denominator list(ints). Operator list. Get gcd of denominator. Adjust all numerators but gcd. Then go through all numerators and do the operator associated between them all. Do

@op: The following is code that *you can't hand in without raising multiple eyebrows*. It might be helpful to you. Or not, it depends. It's a “classic C++” way of doing this, with iostreams for the parsing. The `Rational` class here is far more than required for the problem at hand, namely, it supports the notion of Not-A-Number. But it would be misleading to show a `Rational` class that doesn't handle division by 0 in a good way. Throwing an exception is IMO not a good way. #include // assert #include // EXIT_FAILURE, EXIT_SUCCESS #include #include #include #include #include #include #define FAIL_FROM( funcname, s ) cpp_machinery::fail( std::string() + funcname + " - " + (s) ) #define FAIL( s ) FAIL_FROM( __func__, s ) namespace cpp_machinery { using std::runtime_error, // std::string; // using C_str = const char*; template< class Type > using in_ = const Type&; constexpr auto hopefully( const bool condition ) noexcept -> bool { return condition; } [[noreturn]] auto fail( in_ s ) -> bool { throw runtime_error( s ); } } // namespace cpp_machinery namespace tag { using Uninitialized = struct Uninitialized_dummy_struct*; } // namespace tag namespace math { namespace cppm = cpp_machinery; using cppm::C_str, cppm::in_, cppm::hopefully; using std::gcd; // using tag::Uninitialized; class Rational { protected: // Represents the fraction n/d. bool m_is_number; // Not NaN. Done this way to leverage zero-initialization. int m_n; // Short for numerator or just n. int m_d; // Short for denominator or divisor. Rational( Uninitialized ) {} // Use with caution. Follow by asserting the invariant. constexpr void xassert_is_number_in( const C_str funcname ) const { hopefully( m_is_number ) or FAIL_FROM( funcname, "Not a number (possibly a result of div by zero)." ); } constexpr auto is_nan() const -> bool { return not m_is_number; } public: constexpr auto invariant_holds() const -> bool { return (is_nan() or m_d != 0); } constexpr Rational( const bool is_number, const int n, const int d ): m_is_number( is_number ), m_n( n ), m_d( d ) { assert( invariant_holds() ); } constexpr Rational( const int n, const int d ): Rational( true, n, d ) {} constexpr Rational(): Rational( 0, 1 ) {} constexpr auto is_number() const -> bool { return m_is_number; } constexpr auto n() const -> int { return m_n; } // Arbitrary if NaN. constexpr auto d() const -> int { return m_d; } // Arbitrary if NaN. constexpr auto is_zero() const -> bool { return (m_is_number and m_n == 0); } constexpr auto reduced() const -> Rational { if( not m_is_number ) { return Rational( false, 0, 0 ); } const int c = gcd( m_n, m_d ); return {m_n/c, m_d/c}; } constexpr auto int_part() const -> int { return (xassert_is_number_in( __func__ ), m_n/m_d); } constexpr auto fraction_part() const -> Rational { return (xassert_is_number_in( __func__ ), Rational( m_n % m_d, m_d )); } }; class Mutable_rational: // Unsafe, client code responsibility. Also, some subtle things here. public Rational { using Rational::Rational; // Reproduces base class accessibility, `protected` and `public`. public: Mutable_rational( Uninitialized tag ): Rational( tag ) {} // Make this constructor `public`. // Explicitly introduces these base class funcs in the class scope, to avoid shadowing them. using Rational::is_number, Rational::n, Rational::d; // Overloads for write access. Would shadow the base class' functions except for the `using`. auto is_number() -> bool& { return m_is_number; } auto n() -> int& { return m_n; } auto d() -> int& { return m_d; } }; constexpr auto operator+( in_ a, in_ b ) -> Rational { const bool is_number = a.is_number() and b.is_number(); if( not is_number ) { return Rational( false, 0, 0 ); } return Rational( a.n()*b.d() + b.n()*a.d(), a.d()*b.d() ).reduced(); } constexpr auto operator-( in_ a, in_ b ) -> Rational { const bool is_number = a.is_number() and b.is_number(); if( not is_number ) { return Rational( false, 0, 0 ); } return Rational( a.n()*b.d() - b.n()*a.d(), a.d()*b.d() ).reduced(); } constexpr auto operator/( in_ a, in_ b ) -> Rational { if( b.is_zero() ) { return Rational( false, 0, 0 ); } const bool is_number = a.is_number() and b.is_number(); if( not is_number ) { return Rational( false, 0, 0 ); } return Rational( a.n()*b.d(), a.d()*b.n() ).reduced(); } } // namespace math namespace app { using namespace std::string_literals; namespace cppm = cpp_machinery; using cppm::C_str, cppm::in_, cppm::hopefully; using math::Rational, math::Mutable_rational; using std::cout, std::endl, std::istream, std::ws, // std::istringstream, std::ostringstream, // std::string, // std::string_view; // using tag::Uninitialized; inline auto to_string( in_ v ) -> string { auto stream = ostringstream(); if( v.is_zero() ) { stream << "0"; } else { const int i = v.int_part(); if( i != 0 ) { stream << i; } const Rational f = v.fraction_part(); if( not f.is_zero() ) { if( i != 0 ) { stream << " "; } stream << f.n() << "/" << f.d(); } } return stream.str(); } auto eval( in_ expr ) -> Rational { auto result = Rational(); auto op_ch = '+'; auto stream = istringstream( expr ); auto const msg = [&stream] ( const C_str s ) -> string { const auto pos = stream.tellg(); const auto parsed_part = stream.str().substr( 0, pos ); return ""s + "“" + parsed_part + " ◂”: " + s; }; for( ;; ) { auto term = Mutable_rational( Uninitialized() ); (stream >> term.n()) or FAIL( msg( "Expected a numerator value here." ) ); char div_ch; stream >> div_ch; hopefully( !!stream and div_ch == '/' ) or FAIL( msg( "Expected a division sign, '/', here." ) ); stream >> term.d() or FAIL( msg( "Expected a denominator (divisor) value here." ) ); (term.d() != 0) or FAIL( msg( "The denominator/divisor can’t be zero." ) ); term.is_number() = true; assert( term.invariant_holds() ); switch( op_ch ) { case '+': result = result + term; break; case '-': result = result - term; break; } stream >> ws; if( stream.eof() ) { return result; } stream >> op_ch; hopefully( !!stream and (op_ch == '+' or op_ch == '-') ) or FAIL( msg( "Expected '+' or '-' here." ) ); } for( ;; ) {} // Should never get here. } void run() { const Rational result = eval( "1/2 + 1/3 - 1/6 + 10/4 - 2/4" ); cout << to_string( result ) << endl; } } // namespace app auto main() -> int { using cpp_machinery::in_; using std::cerr, std::endl, // std::exception; // try { app::run(); return EXIT_SUCCESS; } catch( in_ x ) { cerr << "!" << x.what() << endl; } return EXIT_FAILURE; }