精华内容
下载资源
问答
  • 括号匹配 算法

    2016-10-30 02:17:08
    括号匹配算法
    题目链接:点击打开链接
    

    我原来有一个解题方法, 是动态规划, 不过思路不清晰


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

    别人解题报告链接 点击打开链接


    下面说一下我是如何简化的

    原来的思路, 在于下面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;
    }


    展开全文
  • 括号匹配算法

    2015-07-13 00:28:34
    C语言的括号匹配算法,用了栈,数据结构栈的应用的常用程序
  • 括号匹配算法题目来自网络搜集和常考算法,如有侵权请联系我题目描述给出一个仅包含字符'(',')','{','}','['和']',的字符串,判断给出的字符串是否是合法的括号序列括号必须以正确的顺序关闭,"()"和"()[]{}"都是...

    括号匹配算法

    题目来自网络搜集和常考算法,如有侵权请联系我

    题目描述

    给出一个仅包含字符'(',')','{','}','['和']',的字符串,判断给出的字符串是否是合法的括号序列

    括号必须以正确的顺序关闭,"()"和"()[]{}"都是合法的括号序列,但"(]"和"([)]"不合法。

    示例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列表实现一个栈的结构,再使用栈实现括号匹配的算法,所谓的括号匹配是指在编程语言中,括号是成...

    使用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}))]"))

    展开全文
  • 易语言源码易语言括号匹配算法源码.rar 易语言源码易语言括号匹配算法源码.rar 易语言源码易语言括号匹配算法源码.rar 易语言源码易语言括号匹配算法源码.rar 易语言源码易语言括号匹配算法源码.rar 易语言源码...
  • 本文实例讲述了Java栈的应用之括号匹配算法。分享给大家供大家参考,具体如下:1、LeetCode官网美网:https://leetcode.com/中文网:https://leetcode-cn.com/英语不咋地,所以选择此处选择中文网来进行测试。2、...

    本文实例讲述了Java栈的应用之括号匹配算法。分享给大家供大家参考,具体如下:

    1、LeetCode官网

    美网:https://leetcode.com/

    中文网 :https://leetcode-cn.com/

    英语不咋地,所以选择此处选择中文网来进行测试。

    2、LeetCode中获取第20号题目

    (1)搜索20号题目

    (2)查看题目

    4c08ad16a8cc1be69b3616fe9e85c080.png

    (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代码验证是否通过

    7cc146d66784747a8752b0335b01bbec.png

    这样就完成了括号匹配的相关要求,而且是通过Leetcode来完成的,我感觉太酷了~

    下一节我们将继续学习一个关于Leetcode的知识。

    希望本文所述对大家java程序设计有所帮助。

    展开全文
  • 括号匹配算法-java实现import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Stack;public class BracketsMatch {public static void main(String[] args) throws Exception {...
  • 其中有一项就是括号匹配的检测。今天我们来谈一谈其中的原理。先上图图片发自简书App再上代码import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Scanner;class Stack{ch...
  • 括号匹配算法.txt

    2020-06-03 12:29:54
    给定一个只包括"(" ")" "{" "}" "[" "]"的字符串,判定字符串是否有效。 利用栈实现c语言括号匹配算法
  • 易语言括号匹配算法源码.rar

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,793
精华内容 717
关键字:

括号匹配算法