{"id":3461,"date":"2018-08-06T22:11:43","date_gmt":"2018-08-07T05:11:43","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3461"},"modified":"2018-09-12T00:02:52","modified_gmt":"2018-09-12T07:02:52","slug":"leetcode-592-fraction-addition-and-subtraction","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-592-fraction-addition-and-subtraction\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 592. Fraction Addition and Subtraction"},"content":{"rendered":"
\n
\n

Problem<\/strong><\/h1>\n

Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be\u00a0irreducible fraction<\/a>. If your final result is an integer, say\u00a02<\/code>, you need to change it to the format of fraction that has denominator\u00a01<\/code>. So in this case,\u00a02<\/code>\u00a0should be converted to\u00a02\/1<\/code>.<\/p>\n

Example 1:<\/b><\/p>\n

Input:<\/b>\"-1\/2+1\/2\"\r\nOutput:<\/b> \"0\/1\"\r\n<\/pre>\n
Example 2:<\/b><\/p>\n
Input:<\/b>\"-1\/2+1\/2+1\/3\"\r\nOutput:<\/b> \"1\/3\"\r\n<\/pre>\n
Example 3:<\/b><\/p>\n
Input:<\/b>\"1\/3-1\/2\"\r\nOutput:<\/b> \"-1\/6\"\r\n<\/pre>\n
Example 4:<\/b><\/p>\n
Input:<\/b>\"5\/3+1\/3\"\r\nOutput:<\/b> \"2\/1\"\r\n<\/pre>\n
Note:<\/b><\/p>\n
    \n
  1. The input string only contains\u00a0'0'<\/code>\u00a0to\u00a0'9'<\/code>,\u00a0'\/'<\/code>,\u00a0'+'<\/code>\u00a0and\u00a0'-'<\/code>. So does the output.<\/li>\n
  2. Each fraction (input and output) has format\u00a0\u00b1numerator\/denominator<\/code>. If the first input fraction or the output is positive, then\u00a0'+'<\/code>\u00a0will be omitted.<\/li>\n
  3. The input only contains valid\u00a0irreducible fractions<\/b>, where the\u00a0numerator<\/b>\u00a0and\u00a0denominator<\/b>\u00a0of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.<\/li>\n
  4. The number of given fractions will be in the range [1,10].<\/li>\n
  5. The numerator and denominator of the\u00a0final result<\/b>\u00a0are guaranteed to be valid and in the range of 32-bit int.<\/li>\n<\/ol>\n<\/div>\n<\/div>\n
    Solution: Math<\/strong><\/h1>\n
    a\/b+c\/d = (a*d + b * c) \/ (b * d)<\/p>\n
    Time complexity: O(n)<\/p>\n
    Space complexity: O(1)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n  string fractionAddition(string expression) {\r\n    int a = 0;\r\n    int b = 1;    \r\n    int c;\r\n    int d;\r\n    char slash;\r\n    istringstream in(expression);\r\n    while (in >> c >> slash >> d) {\r\n      a = a * d + b * c;\r\n      b *= d;\r\n      int gcd = abs(__gcd(a, b));\r\n      a \/= gcd;\r\n      b \/= gcd;      \r\n    }\r\n    return to_string(a) + \"\/\" + to_string(b);\r\n  }\r\n};<\/pre>\n\n<\/div>
    C++\/class<\/h2>\n
    \n\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 0 ms\r\nclass Fraction {\r\npublic:\r\n  Fraction(int a, int b): a_(a), b_(b) {}\r\n  Fraction& operator+=(const Fraction& f) {\r\n    a_ = a_ * f.b_ + b_ * f.a_;\r\n    b_ = b_ * f.b_;\r\n    int d = abs(__gcd(a_, b_));\r\n    a_ \/= d;\r\n    b_ \/= d;\r\n    return *this;\r\n  }\r\n  \r\n  string toString() {\r\n    return to_string(a_) + \"\/\" + to_string(b_);\r\n  }\r\nprivate:\r\n  int a_; \/\/ hold the sign, e.g. can be +-.\r\n  int b_; \/\/ always > 0.\r\n};\r\n\r\nclass Solution {\r\npublic:\r\n    string fractionAddition(string expression) {\r\n      Fraction f(0, 1);\r\n      int a;\r\n      int b;\r\n      char op;\r\n      istringstream in(expression);\r\n      while (in >> a >> op >> b)\r\n        f += Fraction(a, b);  \r\n      return f.toString();\r\n    }\r\n};<\/pre>\n<\/div><\/div>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[369,368,359,31,177],"class_list":["post-3461","post","type-post","status-publish","format-standard","hentry","category-math","tag-class","tag-fraction","tag-gcd","tag-math","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3461","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3461"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3461\/revisions"}],"predecessor-version":[{"id":3916,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3461\/revisions\/3916"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3461"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3461"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3461"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}