Keluarkan kurungan daripada rentetan algebra yang mengandungi operator + dan - menggunakan C++

Diberi rentetan algebra seperti p-(q-r)-s, kita perlu mengeluarkan kurungan dan menukar rentetan itu menjadi rentetan dengan keputusan matematik yang sama. Oleh itu, rentetan p-(q-r)-s ditukar kepada p-q+r-s, memberikan keputusan matematik yang sama. Untuk mencapai matlamat ini, kita boleh menggunakan timbunan dan menjejaki sama ada simbol yang akan datang dalam ungkapan kurungan harus dibalikkan.

• 0 bermaksud + atau tiada flip

• 1 bermaksud - atau flip

Jadi pada setiap bukaan kurungan kami akan menolak 0 atau 1 bergantung kepada sama ada tanda dalam kurungan terbalik. Apabila kita melihat kurungan penutup, kita pop tindanan.

Nota - Kami tidak mempertimbangkan rentetan yang bermula dengan kurungan. Kita perlu membersihkan tali jenis ini. Contohnya, s="(p-(q+r))" mestilah s="p-(q+r)". Dalam kes ini kita boleh dengan mudah menjalankan gelung dari indeks 1 hingga panjang -2 dan kemudian dari 0 hingga panjang -1.

Mari kita lihat beberapa senario input

Dengan mengandaikan input kaedah ialah beberapa jenis data rentetan, dalam senarai hasil kita mendapat ungkapan kecuali kurungan -

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

Andaikan input kaedah bermula dengan kurungan, dalam senarai hasil, kita mendapat ungkapan tanpa kurungan seperti berikut -

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

Nota - Kami tidak mempertimbangkan rentetan bermula dengan kurungan dalam program. Kita perlu membersihkan tali jenis ini. Contohnya, s="(a+(b-c-d)-e)" mestilah s="a+(b-c-d)-e". Dalam kes ini kita boleh dengan mudah menjalankan gelung dari indeks 1 hingga panjang -2 dan kemudian dari 0 hingga panjang -1.

Di sini kita boleh menggunakan ungkapan polinomial termasuk kurungan sebagai input, jadi dalam senarai yang dihasilkan kita mendapat ungkapan seperti ini -

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

Kami menggunakan ini pada polinomial kuadratik, tetapi kaedah ini juga boleh digunakan untuk ungkapan polinomial tertib tinggi.

Contoh

Andaikan kita mempunyai tiga rentetan S1, S2 dan S3 dengan nilai berikut -

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

Jadi mari kita gunakan kaedah C++ untuk mengalih keluar kurungan daripada rentetan di atas yang mengandungi operator + dan -. Berikut ialah program C++ untuk masalah yang diberikan -

#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

Kesimpulan

Kami menggunakan timbunan mudah untuk menjejaki bendera bagi setiap pembukaan kurungan. Kemudian, menggunakan simbol, kami mengubah nilai satu demi satu. Perkara utama ialah memikirkan cara untuk menjejaki menukar simbol dengan kurungan, dan kemudian masalah menjadi lebih mudah.

Atas ialah kandungan terperinci Keluarkan kurungan daripada rentetan algebra yang mengandungi operator + dan - menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!