这是很久之前CSDN上一个朋友问我的一道题：
去除表达式里面多余的（）
检查字符串表达式中的括号是否匹配；
左括号数目同有括号数目不相等即为不匹配；
去除多余的左括号或者右括号，优先保留先出现的括号；
匹配后去除无效的括号：如：((表达式)) 应为(表达式)；
只考虑小括号，不考虑先出现右括号的情况；
要求实现函数： (字符串最长长度为60；表达式正确性不需要考虑)
void Bracket(char* src, char* dst);
如果匹配则通过dst输出原串；
如果不匹配则根据要求去处多于括号后通过dst输出匹配后的串
示例
输入：12+(345*25-34) 输出：12+(345*25-34)
输入：12+(345*(25-34) 输出： 12+(345*25-34)
输入：(12+345)*25)-34 输出： (12+345)*25-34
输入：(543+(256-43)*203))+24 输出：(543+(256-43)*203)+24
输入：((1+2)*((34-2))+((2*8-1) 输出：((1+2)*(34-2)+2*8-1)
/*
用了一个堆栈，其实主要有三个步骤吧：
（1）分别统计左右括号总数以及所在位置存入lp，rp
（2）依据题设先出现的括号优先的原则进行第一次去括号，主要是：
if：lp_num > rp_num，则从右往左去除lp_num - rp_num个左括号
else if：rp_num < lp_num，则从右往左去除rp_num - lp_num个右括号
（3）经过（2）步骤的处理，左右括号数是相等了，那么就只剩下类似((a + b))这种情况需要处理了，这步处理步骤是最复杂的，主要包括：
从左往右扫描原字符串：
a.如果遇到‘（‘则先弹出栈顶的联系‘（‘，直到栈顶元素是‘）’或者栈的容量为1，最后将新的‘（’入栈
b.如果遇到‘）’则按照以下步骤处理：
if(stack.size >= 3)
{
分别弹出栈顶的前三个元素存入p1, p2, p3
//找到（（））结构并判断是否为多余的
if(p1.type == ')' && p2.type == '(' && p3.type == '(' && p2.pos - p3.pos == 1 && i - p1.pos == 1)
{
则标识p1, p2为多余括号，需要去除；
}
将p3重新入栈
}
将')'入栈
其实上述(3)过程就是为了寻找所有的“(())”结构并判断里面的那个“（）”是不是多余的，举个例子：
（（a + b））中里面那个（）肯定是多余的，必须去除；
而((a + b) + c)里面那个（）就不是多余的，不能去除
*/
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stack>
#define maxv(a, b) ((a) >= (b) ? (a) : (b))
#define minv(a, b) ((a) <= (b) ? (a) : (b))
#define MAX_N 60
using namespace std;
bool unValid[MAX_N + 1];
char input[MAX_N + 1];
char output[MAX_N + 1];
int len;
int lp[MAX_N + 1];
int rp[MAX_N + 1];
struct para
{
char type;
int pos;
para(char t, int p)
{
type = t;
pos = p;
}
};
stack<para> pStack;
void Bracket(char* src, char* dst)
{
int i;
//去除多余的右括号
if(lp[0] < rp[0])
{
for(i = rp[0]; i >= lp[0] + 1; i--)
{
unValid[rp[i]] = true;
rp[i] = -1;
}
}
//去除多余的左括号
else if(lp[0] > rp[0])
{
for(i = lp[0]; i >= rp[0] + 1; i--)
{
unValid[lp[i]] = true;
lp[i] = -1;
}
}
//匹配后去除无效的括号：如：((表达式)) 应为(表达式)
for(i = 0; i < len; i++)
{
if(input[i] == '(' && !unValid[i])
{
while(pStack.size() >= 1 && pStack.top().type == ')')
pStack.pop();
pStack.push(para('(', i));
}
else if(input[i] == ')' && !unValid[i])
{
if(pStack.size() >= 3)
{
para p1 = pStack.top();
if(p1.type == ')')
{
pStack.pop();
para p2 = pStack.top();
pStack.pop();
para p3 = pStack.top();
pStack.pop();
if(p1.type == ')' && p2.type == '(' && p3.type == '(' && p2.pos - p3.pos == 1 && i - p1.pos == 1)
{
unValid[p1.pos] = true;
unValid[p2.pos] = true;
}
pStack.push(p3);
}
}
pStack.push(para(')', i));
}
}
int k = 0;
for(i = 0; i < len; i++)
{
if(!unValid[i])
{
dst[k++] = input[i];
}
}
dst[k] = '\0';
}
int main()
{
char ch;
while((ch = getchar()) != 10)
{
input[len++] = ch;
if(ch == '(')
{
lp[0]++;
lp[lp[0]] = len - 1;
}
else if(ch == ')')
{
rp[0]++;
rp[rp[0]] = len - 1;
}
}
Bracket(input, output);
printf("%s\n", output);
return 0;
}
分享到：
相关推荐
Java使用正则表达式去除小数点后面多余的0功能示例 Java语言中使用正则表达式可以实现去除小数点后面多余的0的功能，这个功能示例主要介绍了Java使用正则表达式去除小数点后面多余的0功能，结合具体实例形式分析了...
题目要求编写一个程序，去除给定的四则运算表达式中的多余括号，同时保持原表达式的变量和运算符顺序不变，并确保结果与原始表达式等价。这里不涉及正负号的处理，即假设输入的表达式不会包含`(+a)`或`(-a)`的形式。...
本文将详细介绍如何使用正则表达式来去除浮点数或字符串表示的数值中小数点后多余的零。 #### 一、背景介绍 在实际开发过程中，我们常常会遇到一些数据处理场景，比如货币计算、统计数据等，这些场景下对数值精度...
网上测试了很多，大多数都不满意。于是自己编写了一个。VBA利用通配符或正则表达式删除Word中选中部分的多余空行，支持把手动换行符替换为段落标记处理。
正则表达式在JavaScript中是处理字符串匹配和替换的强大工具，尤其在去除字符串中的空格和换行时非常有效。空格和换行符在文本处理中经常会成为困扰，特别是在处理用户输入或从外部源获取的数据时。如果不正确处理，...
在处理SQL格式化问题时，去除多余的空格和换行后，可能还需要确认SQL语句是否已经是分页SQL。可以通过编写一个方法使用正则表达式 `(?i).+LIMIT[\\d+*|\\d*,*\\d+].+` 来判断一条SQL语句是否包含LIMIT关键字及其参数...
在pdf转为文本的时候，经常会多出空格，影响数据观感，因此需要去掉文本中多余的空格，而文本中的英文之间的正常空格需要保留，输入输出如下： input：我今天 赚了 10 个亿，老百姓very happy。 output：我今天赚了...
此表达式用于去除字符串开头`(^)`和结尾`($)`的空白字符`\s`。在处理用户输入或文本文件时，这可以帮助标准化文本格式。 ### 6. 匹配Email地址 正则表达式：`\w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*` 这是...
该算法的核心思想是首先对输入的文法和句子进行词法分析，去除多余的字符，并将产生式和终结符、非终结符填入有关数组，为语法分析做前期准备。然后，使用算符优先关系表来判断算术表达式的正确性。 二、算符优先...
- **用途**：去除文本中的多余空白行。 #### 四、匹配HTML标记的正则表达式：<(\S*?)[^>]*>.*?|*?> - **应用场景**：用于去除HTML代码中的标签。 - **解释**：此表达式尝试匹配简单的HTML标签结构，但可能无法处理...
- **数据清洗**：去除文本中的噪声，如HTML标签、多余的空格等。 通过以上介绍，我们可以看到Python中的正则表达式是一个非常强大的工具，可以帮助我们解决实际工作中遇到的各种问题。理解并掌握这些基本概念和用法...
- **应用场景**: 输入验证时，确保用户提交的信息没有多余的前导或尾随空格。 #### 6. 邮箱地址验证 **正则表达式**: `\w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*` - **用途**: 用于验证邮箱地址格式是否正确。 ...
Java 去掉文本中多余的空格与空行实例代码 Java 去掉文本中多余的空格与空行实例代码主要介绍了如何使用 Java 语言去掉文本中多余的空格与空行。该代码主要用于解决在开发小型圈子系统时出现的问题，即用户在圈子...
此表达式用于匹配空白区域，如去除字符串中的多余空格。 4. **匹配HTML标签**：`<(S*?)[^>]*>.*?|*?/>` - 此表达式用于提取或删除HTML文档中的标签，包括自闭合标签。`S`代表空白字符，`[^>]*`匹配任何不包括`>`的...
正则表达式中的特殊字符 字符 含意 \ 做为转意，即通常在"\"后面的字符不按原来意义解释，如/b/匹配字符"b"，当b前面加了反斜杆后/\b/，转意为匹配一个单词的边界。 -或- 对正则表达式功能字符的还原，如"*"匹配它...
- 数据清洗：删除或替换不符合规则的数据，如去除多余的空格、特殊字符等。 - 分割字符串：根据特定的分隔符拆分字符串成多个部分。 7. **性能考虑**： 使用正则表达式可能会对查询性能产生影响，尤其是在大数据...
- **数据清洗**: 清理数据中的多余空白，使数据更加整洁。 **示例代码**: ```javascript let str = " 欢迎访问我们的网站 "; let re = /[\s|]*\r/g; let trimmed = str.replace(re, ""); console.log(trimmed); // ...
为了实现这一目的，可以使用正则表达式技术来匹配并去除HTML标签，仅保留文本内容。 正则表达式是一种强大的文本匹配模式，它允许用户定义一个搜索模式，用来在文本中搜索符合该模式的字符串。使用正则表达式去除...