Validation of Equation Given as String

0 0 6 minutes read

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 I

Input: 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 valid
bool 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 code
int main()
{
    string str = "2+5+3+1=11";
    if (isValid(str))
        cout << "Valid";
    else
        cout << "Invalid";
 
    return 0;
}

Java

// Java implementation of the approach
import 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 approach
using 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 valid
function 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 code
let 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 zambiatek!