Last Updated: 19 Apr, 2021
Ayush and Expression
Moderate
Asked in companies
Ayush read about irreducible fractions in the school and made an expression ‘EXPRESSION’ of fraction addition and subtraction.
Note:
An irreducible fraction is a fraction in which the numerator and denominator are integers that have no other common divisors than 1.
Example: 2/3, 8/9, 0/1 are irreducible fractions, where 8/12, 9/12 are not irreducible fractions.
Expression ‘EXPRESSION’ contains integers from '0' to '9', and characters '/', '+' and '-'.
Each fraction will be an irreducible fraction and will be in the format of ±(numerator/denominator).
Ayush does not know how to solve the expression he made, so he gave you the expression to solve. Your task is to solve the expression.
Note:
Ayush expects your answer to be an irreducible fraction, so if your answer is an integer, convert it into an irreducible fraction by putting 1 in the denominator.
For example, if your answer is "9", then print "9/1" (without quotes).
Input format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains a string ‘EXPRESSION’, representing the expression that you need to solve.
Note:
The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10].
Output format:
For each test case, return the irreducible fraction after solving the expression.
Output for each test case is printed on a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= |EXPRESSION| <= 10^5
‘EXPRESSION’ will only contain integers from '0' to '9', and characters '/', '+' and '-'.
Time Limit: 1 sec
Approaches
We can use brute force to solve the problem. We can simplify this problem by making all denominators equal. This can be done by finding the least common multiple of all the denominators.
First, store the fractions in an array. Then, rewrite the expression such that each fraction will have a common denominator. Now, expression can be easily solved by only solving all the numerators. After that, convert the final expression into an irreducible fraction.
Algorithm:
- First, extract all the fractions with a sign and store them in an array let’s say ‘ARR’. A fraction can be found by splitting ‘EXPRESSION’ based on ‘+’ and ‘-’ characters, which can be done by finding the next ‘+’ or ‘-’ character in the STR, and the string between that will be the fraction.
- For example, if ‘EXPRESSION’ = 1/2-3/4 from index 0 in ‘EXPRESSION’ the next ‘+’ or ‘-’ character is at index 3 so from substring [0, 3) is a fraction. Similarly, the next fraction between indices [3,6] will be -3/4.
- Consider we have an ‘N’ number of fractions {F1, F2, F3,..., Fn}, which have corresponding numerators {N1, N2, N3, ..., Nn} and denominators {D1, D2, D3, ..., Dn}.
- Consider a variable ‘LCM’ initialized with value = 1, which is the least common multiple of all the denominators.
- We can rewrite our expression in the form of
- Fi = ((LCM / Di) * Ni) / LCM, here Ni = (LCM / Di) * Ni, and Di = LCM.
- After that, we will add all the numerators and store them in a variable ‘X’, and denominator ‘Y’ = LCM.
- After that, our final expression will be X / Y. Convert the final expression into an irreducible fraction. To convert into irreducible fraction find GCD of numerator and denominator, then divide both by GCD.
We can solve this problem as we iterate over ‘EXPRESSION’ and solve the fractions sequentially. To do this we need to maintain the overall result in the form of X / Y.
For each fraction part in the form of A / B, where A is the numerator and B is the denominator. Here we are solving X / Y + A / B so after taking LCM, the result will be (X * B + Y * A) / Y * B. Convert it into an irreducible fraction by removing the common divisor.
Algorithm:
- Consider two variables ‘X’ and ‘Y’ with initial values ‘X’ = 0 and ‘Y’ = 1.
- Traverse on the expression, on each fraction
- Parse the fraction in variable ‘A’ as a numerator and variable ‘B’ as a denominator.
- Assign ‘X’ = (X * B + Y * A) and ‘Y’ = Y * B
- Convert it into an irreducible fraction by removing the common divisor. To do this, find ‘GCD’ = GCD(X, Y), update ‘X’ = X / G and ‘Y’ = Y / G.
- Repeat the steps again till there are no more fractions.