题目链接：点击打开链接
我原来有一个解题方法, 是动态规划, 不过思路不清晰


后来看了别人的解题, 与人讨论这个解题报告, 发现可以简化很多
别人解题报告链接 点击打开链接


下面说一下我是如何简化的
原来的思路, 在于下面4点

①若S为 [S'] 或 (S'),则我们只需要把 S' 串变成规则的就可以了。

②若S为[S' 或 (S' ，则我们只需要把 S‘ 串变成规则的，最后再加一个] 或)就可以了。

③若S为 S'] 或 S'),则我们只需要把 S’ 串变成规则的，最后再在前面加一个[或(就可以了。

④若找S[i……j]变成规则的最小数目，就是S[i……k] 和 S[k+1……j] 最小数目找出来相加（区间DP的分区间）



其中2和3可以去掉
为什么呢, 因为在第四条里面, 当k=i 或者k=j的时候, 就是前面或者后面不匹配
不匹配的符号, 都是一个一个的加上字符, 让他匹配

所以 只需要 一个一个的加就行了


最后是最终的代码

 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define check(i,j) ((s[i]=='['&&s[j]==']')||(s[i]=='('&&s[j]==')'))
#define min(a,b) ((a)<(b)?(a):(b))
#define INF 1000000
int dp[101][101];
char s[101];

int preHandleStr(char *s, int len){
	int last=len-1,i,j;
	for (i=0; i<last;){
		if (check(i,i+1)){
			memmove(s+i, s+(i+2), len-(i+2));
			len -= 2;
			last -= 2;
			
			if (i > 0) --i;
		}
		else
			++i;
	}
	
	s[len] = 0;
	return len;
}

int main()
{
    int T,i,j,k,p,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        n=strlen(s);
	n=preHandleStr(s,n);
		
        for(i=1;i<n;i++)
            dp[i][i-1]=0;
        for(i=0;i<n;i++)
            dp[i][i]=1;
        for(p=1;p<n;p++)
            for(i=0;i<=n-p;i++)
            {
                j=i+p;
                dp[i][j]=INF;
                if (check(i,j))
                    dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
                for(k=i;k<j;k++)
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
        printf("%d\n",dp[0][n-1]);
    }
    return 0;
}

括号匹配算法
题目来自网络搜集和常考算法，如有侵权请联系我
题目描述
给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
示例1
输入
"["
输出
false
示例2
输入
"[]"
输出
true
C++
#include
class Solution {
public:
/**
*
* @param s string字符串
* @return bool布尔型
*/
bool isValid(string s) {
// write code here
unordered_map m = { {')','('},{']','['},{'}','{'} };
stack st;
int len=s.length();
for (int i=0;i
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
st.push(s[i]);
}
else if (st.empty())  return false;
else if (st.top() != m[s[i]]) return false;
else st.pop();
}
return st.empty();
}
};
C语言
#include 
#include 
int top=-1;//top变量时刻表示栈顶元素所在位置
void push(char * a,int elem){
a[++top]=elem;
}
void pop(char* a){
if (top==-1) {
return ;
}
top--;
}
char visit(char * a){
//调取栈顶元素，不等于弹栈，如果栈为空，为使程序不发生错误，返回空字符
if (top!=-1) {
return a[top];
}else{
return ' ';
}
}
int main() {
char a[30];
char bracket[100];
printf("请输入括号序列：");
scanf("%s",bracket);
getchar();
int length=(int)strlen(bracket);
for (int i=0; i
//如果是左括号，直接压栈
if (bracket[i]=='('||bracket[i]=='{') {
push(a, bracket[i]);
}else{
//如果是右边括号，判断与栈顶元素是否匹配，如果匹配，栈顶元素弹栈，程序继续运行；否则，发现括号不匹配，输出结果直接退出
if (bracket[i]==')') {
if (visit(a)=='(') {
pop(a);
}else{
printf("括号不匹配");
return 0;
}
}else{
if (visit(a)=='{') {
pop(a);
}else{
printf("括号不匹配");
return 0;
}
}
}
}
//如果所有括号匹配完成，栈内为空，说明所有括号全部匹配成功
if (top!=-1) {
printf("括号不匹配");
}else{
printf("括号匹配");
}
}
Java
import java.util.Stack;
public class Solution {
public boolean isValid(String s) {
Stack stack = new Stack();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.isEmpty() || stack.pop() != c)
return false;
}
return stack.isEmpty();
}
}

使用Python的栈实现括号匹配算法
发布时间：2020-08-05 22:12:19
来源：51CTO
阅读：293
作者：wx5a4c600866558
利用Python列表实现一个栈的结构，再使用栈实现括号匹配的算法，所谓的括号匹配是指在编程语言中，括号是成对出现的，最先出现的左括号，对应于最后的右括号，后出现的左括号对应于最新右括号，符合栈的特征
写一个栈的类：stack.py
class Stack:
def __init__(self):
self.items = []
def is_Empty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(items)-1]
def size(self):
return len(self.items)
实现括号匹配的算法程序：
from stack import Stack
def parChecker(symbolString):
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol == "(":
s.push(symbol)
elif symbol == ")":
if s.is_Empty():
balanced = False
else:
s.pop()
index += 1
if balanced and s.is_Empty():
return True
else:
return False
print(parChecker("(((2356)))"))
输出结果：
True
再测试
print(parChecker("(()))"))
输出结果False
扩展
能够匹配多种括号，{},[]
只需要小小的改动代码：
from stack import Stack
def parChecker(symbolString):
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol in "({[":
s.push(symbol)
elif symbol in ")}]":
if s.is_Empty():
balanced = False
else:
s.pop()
index += 1
if balanced and s.is_Empty():
return True
else:
return False
print(parChecker("[(({fdf}))]"))

本文实例讲述了Java栈的应用之括号匹配算法。分享给大家供大家参考，具体如下：
1、LeetCode官网
美网：https://leetcode.com/
中文网 ：https://leetcode-cn.com/
英语不咋地，所以选择此处选择中文网来进行测试。
2、LeetCode中获取第20号题目
(1)搜索20号题目
(2)查看题目
(3)根据题目要求，首先在本地编辑器中完善20号题目的代码--使用java提供的Stack类，代码如下：
class Solution {
public boolean isValid(String s) {
Stack stack=new Stack();
for (int i=0;i
char c=s.charAt(i);
if(c=='('||c=='['||c=='{'){
stack.push(c);
}else {
if(stack.isEmpty())
return false;
char topChar=stack.pop();
if(c==')'&&topChar!='(')
return false;
if (c==']'&&topChar!='[')
return false;
if(c=='}'&&topChar!='{')
return false;
}
}
return stack.isEmpty();
}
}
(4)将代码提交到LeetCode代码验证是否通过
这样就完成了括号匹配的相关要求，而且是通过Leetcode来完成的，我感觉太酷了~
下一节我们将继续学习一个关于Leetcode的知识。
希望本文所述对大家java程序设计有所帮助。