Given a string in the form of an equation i.e A + B + C – D = E where A, B, C, D and E are integers and -, + and = are operators. The task is to print Valid if the equation is valid else print Invalid.
Note: String only comprises of the characters from the set {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, =}.
Examples:
Input: str = “1+1+1+1=7”
Output: Invalid IInput: str = “12+13-14+1=12”
Output: Valid
Approach:
- Traverse the string and store all the operands in an array operands[] and all the operators in an array operators[].
- Now perform the arithmetic operation stored in operators[0] on operands[0] and operands[1] and store it in ans.
- Then perform the seconds arithmetic operation i.e. operators[1] on ans and operators[2] and so on.
- Finally, compare the ans calculated with the last operand i.e. operands[4]. If they’re equal then print Valid else print Invalid.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if the equation is validbool isValid(string str){ int k = 0; string operands[5] = ""; char operators[4]; long ans = 0, ans1 = 0, ans2 = 0; for (int i = 0; i < str.length(); i++) { // If it is an integer then add it to another string array if (str[i] != '+' && str[i] != '=' && str[i] != '-') operands[k] += str[i]; else { operators[k] = str[i]; // Evaluation of 1st operator if (k == 1) { if (operators[k - 1] == '+') ans += stol(operands[k - 1]) + stol(operands[k]); if (operators[k - 1] == '-') ans += stol(operands[k - 1]) - stol(operands[k]); } // Evaluation of 2nd operator if (k == 2) { if (operators[k - 1] == '+') ans1 += ans + stol(operands[k]); if (operators[k - 1] == '-') ans1 -= ans - stol(operands[k]); } // Evaluation of 3rd operator if (k == 3) { if (operators[k - 1] == '+') ans2 += ans1 + stol(operands[k]); if (operators[k - 1] == '-') ans2 -= ans1 - stol(operands[k]); } k++; } } // If the LHS result is equal to the RHS if (ans2 == stol(operands[4])) return true; else return false;}// Driver codeint main(){ string str = "2+5+3+1=11"; if (isValid(str)) cout << "Valid"; else cout << "Invalid"; return 0;} |
Java
// Java implementation of the approachimport java.util.*;public class GFG { // Function that returns true if the equation is valid static boolean isValid(String str) { int k = 0; String[] operands = new String[5]; for (int i = 0; i < 5; i++) { operands[i] = ""; } char[] operators = new char[4]; long ans = 0, ans1 = 0, ans2 = 0; for (int i = 0; i < str.length(); i++) { // If it is an integer then add it to another // string array if (str.charAt(i) != '+' && str.charAt(i) != '=' && str.charAt(i) != '-') operands[k] += str.charAt(i); else { operators[k] = str.charAt(i); // Evaluation of 1st operator if (k == 1) { if (operators[k - 1] == '+') ans += Integer.valueOf( operands[k - 1]) + Integer.valueOf( operands[k]); if (operators[k - 1] == '-') ans += Integer.valueOf( operands[k - 1]) - Integer.valueOf( operands[k]); } // Evaluation of 2nd operator if (k == 2) { if (operators[k - 1] == '+') ans1 += ans + Integer.valueOf( operands[k]); if (operators[k - 1] == '-') ans1 -= ans - Integer.valueOf( operands[k]); } // Evaluation of 3rd operator if (k == 3) { if (operators[k - 1] == '+') ans2 += ans1 + Integer.valueOf( operands[k]); if (operators[k - 1] == '-') ans2 -= ans1 - Integer.valueOf( operands[k]); } k++; } } // If the LHS result is equal to the RHS if (ans2 == Integer.valueOf(operands[4])) return true; else return false; } // Driver code public static void main(String args[]) { String str = "2+5+3+1=11"; if (isValid(str)) System.out.print("Valid"); else System.out.print("Invalid"); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python3 implementation of the approach # Function that returns true if # the equation is valid def isValid(string) : k = 0; operands = [""] * 5 ; operators = [""] * 4 ; ans = 0 ; ans1 = 0; ans2 = 0; for i in range(len(string)) : # If it is an integer then add # it to another string array if (string[i] != '+' and string[i] != '=' and string[i] != '-') : operands[k] += string[i]; else : operators[k] = string[i]; # Evaluation of 1st operator if (k == 1) : if (operators[k - 1] == '+') : ans += int(operands[k - 1]) + int(operands[k]); if (operators[k - 1] == '-') : ans += int(operands[k - 1]) - int(operands[k]); # Evaluation of 2nd operator if (k == 2) : if (operators[k - 1] == '+') : ans1 += ans + int(operands[k]); if (operators[k - 1] == '-') : ans1 -= ans - int(operands[k]); # Evaluation of 3rd operator if (k == 3) : if (operators[k - 1] == '+') : ans2 += ans1 + int(operands[k]); if (operators[k - 1] == '-') : ans2 -= ans1 - int(operands[k]); k += 1 # If the LHS result is equal to the RHS if (ans2 == int(operands[4])) : return True; else : return False; # Driver code if __name__ == "__main__" : string = "2 + 5 + 3 + 1 = 11"; if (isValid(string)) : print("Valid"); else : print("Invalid"); # This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;class GFG { // Function that returns true if the equation is valid static bool isValid(string str) { int k = 0; string[] operands = new string[5]; char[] operators = new char[4]; long ans = 0, ans1 = 0, ans2 = 0; for (int i = 0; i < str.Length; i++) { // If it is an integer then add it to another // string array if (str[i] != '+' && str[i] != '=' && str[i] != '-') operands[k] += str[i]; else { operators[k] = str[i]; // Evaluation of 1st operator if (k == 1) { if (operators[k - 1] == '+') ans += Int64.Parse(operands[k - 1]) + Int64.Parse(operands[k]); if (operators[k - 1] == '-') ans += Int64.Parse(operands[k - 1]) - Int64.Parse(operands[k]); } // Evaluation of 2nd operator if (k == 2) { if (operators[k - 1] == '+') ans1 += ans + Int64.Parse(operands[k]); if (operators[k - 1] == '-') ans1 -= ans - Int64.Parse(operands[k]); } // Evaluation of 3rd operator if (k == 3) { if (operators[k - 1] == '+') ans2 += ans1 + Int64.Parse(operands[k]); if (operators[k - 1] == '-') ans2 -= ans1 - Int64.Parse(operands[k]); } k++; } } // If the LHS result is equal to the RHS if (ans2 == Int64.Parse(operands[4])) return true; else return false; } // Driver code public static void Main() { string str = "2+5+3+1=11"; if (isValid(str)) Console.Write("Valid"); else Console.Write("Invalid"); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// Javascript implementation of the approach// Function that returns true if the equation is validfunction isValid(str){ let k = 0; let operands = []; for (let i = 0; i < 5; i++) { operands[i] = ""; } let operators = [] let ans = 0; let ans1 = 0; let ans2 = 0; for (let i = 0; i < str.length; i++) { // If it is an integer then add it to another // string array if (str[i] != '+' && str[i] != '=' && str[i] != '-') operands[k] += str[i]; else { operators[k] = str[i]; // Evaluation of 1st operator if (k == 1) { if (operators[k - 1] == '+') ans += parseInt(operands[k - 1]) + parseInt(operands[k]); if (operators[k - 1] == '-') ans += parseInt(operands[k - 1]) - parseInt(operands[k]); } // Evaluation of 2nd operator if (k == 2) { if (operators[k - 1] == '+') ans1 += ans + parseInt(operands[k]); if (operators[k - 1] == '-') ans1 -= ans - parseInt(operands[k]); } // Evaluation of 3rd operator if (k == 3) { if (operators[k - 1] == '+') ans2 += ans1 + parseInt(operands[k]); if (operators[k - 1] == '-') ans2 -= ans1 - parseInt(operands[k]); } k++; } } // If the LHS result is equal to the RHS if (ans2 == parseInt(operands[4])) return true; else return false;}// Driver codelet str = "2+5+3+1=11";if (isValid(str)) document.write("Valid");else document.write("Invalid");// This code is contributed by Samim Hossain Mondal.</script> |
Output
Valid
Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Information on that Topic: geeksforgeeks.org/validation-of-equation-given-as-string/ […]