Remove brackets from algebraic string containing + and - operators using C++

Given an algebraic string like p-(q-r)-s, we need to remove the parentheses and convert the string into a string with the same mathematical result. Therefore, the string p-(q-r)-s is converted to p-q r-s, giving the same mathematical result. To achieve this, we can use the stack and keep track of whether the upcoming symbol in the bracket expression should be flipped.

• 0 means or no flip

• 1 means - or flip

So at each bracket opening we will push 0 or 1 depending on whether the sign in the bracket is flipped. When we see the closing bracket, we pop the stack.

Note - We do not consider strings starting with parentheses. We have to clean this type of string. For example s="(p-(q r))" must be s="p-(q r)". In this case we can easily run a loop from index 1 to length -2 and then from 0 to length -1.

Let’s look at some input scenarios

Assuming that the input of the method is a number of string data type, in the result list, we get the expression except the brackets -

Input: (2×3)─(6─(4+5))
Result: 2×3–6+4+5

Assuming that the input of the method starts with parentheses, in the result list, we get an expression without parentheses, as follows -

Input: (a+(b-c-d)-e)
Result: a-b+c+d+e

Note - We do not consider strings starting with parentheses in the program. We have to clean this type of string. For example, s="(a (b-c-d)-e)" must be s="a (b-c-d)-e". In this case we can easily run a loop from index 1 to length -2 and then from 0 to length -1.

Here we can use a polynomial expression containing parentheses as input, so in the result list, we get the following expression -

Input: (p*p)-(p-q)
Result: p*p-p+q

We applied this to quadratic polynomials, but the method can also be used for higher-order polynomial expressions.

Example

Suppose we have three strings S1, S2 and S3 with the following values ​​-

string s1 = "p-(-q+(-r+(s-t)))";
string s2 = "(p+q-r+t+u)";
string s3 = "(p+ (q-r-t)-u)";

So, let us use C method to remove brackets from above string containing and - operators. Here is a C program for the given problem -

#include <iostream>
#include <stack>
using namespace std;
string solve(string s) {
   stack<int> sk;
   sk.push(0);
   string res = "";
   for(int i=0;i<s.size();i++) {
      if(s[i] == '(') {
         int temp = s[i-1] == '+' ? 0 : 1;
         if(sk.top() == 0) sk.push(temp);
         else sk.push(temp^1);
      } else if(s[i] == ')') {
         sk.pop();
      } else if(s[i] == '+' || s[i] == '-') {
         char op;
         if(sk.top() == 0) op = s[i];
         else op = (s[i]=='+' ? '-' : '+');
         if(res.size() != 0 && (res[res.size()-1]=='+' || res[res.size()- 1]=='-')) res[res.size()-1] = op;
         else res+=op;
      } else {
         res+=s[i];
      }
   }
   return res;
}
int main() {
   string s1 = "p-(-q+(-r+(s-t)))";
   string s2 = "(p+q-r+t+u)";
   string s3 = "(p+ (q-r-t)-u)";
   cout << solve(s1) << endl;
   cout << solve(s2) << endl;
   cout << solve(s3) << endl;
   return 0;
}

Output

p+q+r-s+t
p-q+r-t-u
p- q-r-t+u

in conclusion

We use a simple stack to keep track of the flags for each bracket opening. Then, using symbols, we transform the values ​​one by one. The key is to figure out how to keep track of changing symbols with parentheses, and then the problem becomes easier.

The above is the detailed content of Remove brackets from algebraic string containing + and - operators using C++. For more information, please follow other related articles on the PHP Chinese website!