去除表达式里面多余的（）

 

这是很久之前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;
}

 

 

我没看你的代码！所以不知道你是怎么实现的！
我的思路

用个队列！放入括号的左边部分 （用一个数组记录在字符串的索引） 遇到一个匹配的右括号  弹出队列！！

到最后看队列有没有值！有说明不匹配！！然后根据记录的索引！去除哪个字符！

每太看懂你的意思，不过我感觉不对，（（a + b））你的处理步骤是什么？

你多跑几个例子看看吧，这个东西没那么简单，还是蛮复杂的。用队列是对的，但是还有一系列的处理逻辑

import java.util.LinkedList;
import java.util.Queue;



public class RemoveBrackets {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

cute("(12+345)*25)-34");
cute("12+(345*(25-34)");
}
public static void cute(String str)
{
char[]datas=str.toCharArray();
Queue qd=new LinkedList();
//Queue rq=new LinkedList();
Queue lq=new LinkedList();
Queue qd2=new LinkedList();
int j=0;
for(int i=0;i<datas.length;i++)
{
if(datas[i]=='(')
{
qd.add(i);
lq.add(datas[i]);
}
if(datas[i]==')')
{
if(lq.size()>0)
{
lq.remove();
qd.remove();
}
else
{
//rq.add(datas[i]);
qd2.add(i);
}

}
}
Integer in;
for(int i=0;i<qd.size();i++)
{
//System.out.println("1");
in=(Integer)qd.remove();
datas[in]=' ';
}

for(int i=0;i<qd2.size();i++)
{
//System.out.println("2");
in=(Integer)qd2.remove();
datas[in]=' ';
}
System.out.println(new String(datas).replaceAll(" ",""));

}

}

我实现了一些！！

一个队列是不能解决！！

用了三个队列！比用数组应该简单！！

我就用了一个堆栈，其实主要有三个步骤吧：
（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重新入栈
                        }
                        将')'入栈

其实上述过程就是为了寻找所有的“(())”结构并判断里面的那个“（）”是不是多余的，举个例子：
（（a + b））中里面那个（）肯定是多余的，必须去除；
而((a + b) + c)里面那个（）就不是多余的，不能去除

在我的印象中，括号匹配好像是大学时栈的应用的一个例子

嗯  我看你用了 几个数组！其实队列就是数组！！

其实用队列操作起来更简单！！

就像我上面的代码！！没多少代码量！！

你的代码存在问题

34+)34*(34)

你把这个输入

运行下！！