给定一个像 p-(q-r)-s 这样的代数字符串,我们需要删除括号并将该字符串转换为具有相同数学结果的字符串。因此,字符串 p-(q-r)-s 被转换为 p-q+r-s,给出了相同的数学结果。为了实现这一点,我们可以使用堆栈并跟踪是否应该翻转括号表达式中即将出现的符号。
0 表示 + 或无翻转
1 表示 - 或翻转
因此,在每个括号打开时,我们将根据括号中的符号是否翻转来推送 0 或 1。当我们看到右括号时,我们将弹出堆栈。
注意 - 我们没有考虑以括号开头的字符串。我们必须清理这种类型的字符串。例如 s="(p-(q+r))" 必须是 s="p-(q+r)"。在这种情况下,我们可以轻松地运行从索引 1 到长度 -2,然后从 0 到长度-1 的循环。
让我们看一些输入场景
假设该方法的输入是字符串数据类型的数字,在结果列表中,我们获得除括号外的表达式 -
'Input: (2×3)─(6─(4+5))
Result: 2×3–6+4+5
假设方法的输入以括号开头,在结果列表中,我们得到一个不带括号的表达式,如下 -
'Input: (a+(b-c-d)-e)
Result: a-b+c+d+e
注意 - 我们没有考虑程序中以括号开头的字符串。我们必须清理这种类型的字符串。例如 s="(a+(b-c-d)-e)" 必须是 s="a+(b-c-d)-e"。在这种情况下,我们可以轻松地运行从索引 1 到长度 -2,然后从 0 到长度-1 的循环。
这里我们可以使用包含括号的多项式表达式作为输入,因此在结果列表中,我们获得如下表达式 -
'Input: (p*p)-(p-q)
Result: p*p-p+q
我们将其应用于二次多项式,但该方法也可用于更高阶的多项式表达式。
示例
假设我们有三个字符串 S1、S2 和 S3,其值如下 -
'string s1 = "p-(-q+(-r+(s-t)))";
string s2 = "(p+q-r+t+u)";
string s3 = "(p+ (q-r-t)-u)";
因此,让我们使用 C++ 方法从上面包含 + 和 - 运算符的字符串中删除括号。这是针对给定问题的 C++ 程序 -
'#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;
}
输出
'p+q+r-s+t
p-q+r-t-u
p- q-r-t+u
结论
我们使用一个简单的堆栈来跟踪每个括号开口的标志。然后,用符号,我们把价值观一一转化。关键是要确定如何用括号跟踪变化的符号,之后问题就变得容易了。