算法设计与分析/数据结构与算法实验4:添加括号数目问题

简介: 算法设计与分析/数据结构与算法实验4:添加括号数目问题

1.实验目的

(1)掌握动态规划法的处理思路与算法框架。

(2)掌握应用动态规划法解决具体问题的方法。

(3)掌握动态规划法的广泛应用。

2.实验内容

(1)问题描述

括号序列有()、{}和[]组成。

(1)设计一个算法来判断括号序列不合法,如“(([{}]))”是合法的,而“(}{)”、“(}(}”和“({)}”都是不合法的。

(2)如果一个括号序列不合法,设计一个算法,求解使该序列成为合法的括号序列至少需要添加的括号数目。例如,“(}(}”最少需要添加4个括号成为合法括号序列,即变为“(){}(){}”。

(2)输入

输入只有一行。

第一行包含一个字符串,它的长度为。这个字符串仅由小括号、中括号或大括号,即’(’,’)’,’[’,’]’,’{’或’}’组成。字符的下标从0开始。

(3)输出

输出分为两行。

第一行输出True或False。True表示括号序列是合法序列,False表示括号序列不是合法序列。

第二行输出使该序列成为合法的括号序列至少需要添加的括号数目。

3.问题实例分析

 实例:输入参数str=[({}}。

 首先解决问题1。该括号序列是否为一个合法序列?

 可以利用栈这一数据结构进行解决。遍历当前序列,每碰到一个左括号就入栈,放入栈顶。碰到一个右括号时,判断当前右括号与左括号是否匹配。若匹配,则将左括号出栈。若不匹配,则无需遍历后续括号序列,结束遍历,能直接能说明当前括号序列为不合法序列。在遍历完序列后,若栈不为空,则说明还有左括号没被右括号匹配上。同样的,这也是个不合法的括号序列。

 言而简之,当且仅当括号序列能被遍历完且遍历完时栈为空,括号序列才能为合法序列。

 在本实例中,初始时栈为空,首先将第0个字符左中括号“[”入栈,再将第1个字符左小括号“(”入栈,将第2个字符左大括号“{”入栈。第3个字符为“}”,与栈顶的左大括号“{”匹配了,出栈。第4个字符为“}”,与栈顶“(”不匹配,则说明当前序列不是合法序列。

 解决问题2。求解使该序列成为合法序列所需要添加的最少的括号数目。我们也可以自底向上地解决这个问题。

 先将这个问题分解为若干个规模较小且相等的子问题:只有1个括号时使得括号序列合法化所需的括号数目,只有2个括号时使得括号序列合法化所需的括号数目。3个或多个括号合法化时所需的括号数量可以分解为上述的子问题。

image.png


1
1
1
1
1


image.png

1 2
1 2
1 0
1 2
1

image.png


1 2 3
1 2 1
1 0 1
1 2
1

image.png


1 2 3 2
1 2 1 2
1 0 1
1 2
1

五个字符

1 2 3 2 3
1 2 1 2
1 0 1
1 2
1

image.png


4.算法描述及说明

image.png


5.算法正确性分析

 算法会正确地结束:在运行完成三重循环后,算法会停止。

image.png


7.运行结果展示及其说明

测试样例使用了三组。对于每一组测试样例,都正确地输出了该括号序列是否合法,以及使得括号序列变为合法序列所需的括号数目。

8.心得体会

9.程序源代码

#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
string str;
int dp[1005][1005];
bool check(int i, int j) {
  if ((str[i] == '(') && (str[j] == ')') || (str[i] == '[') && (str[j] == ']') || (str[i] == '{') && (str[j] == '}'))
    return true;
  else return false;
}
int main() {
  cin >> str;
  int maxlen = str.size();
  for (int len = 1; len <= maxlen; len++) {
    for (int l = 0; l + len - 1 < maxlen; l++) {
      int r = l + len - 1;
      if (len == 1)
        dp[l][r] = 1;
      else {
        dp[l][r] = 0x3f3f3f3f;
        if (check(l, r)) {
          dp[l][r] = min(dp[l][r], dp[l + 1][r - 1]);
        }
        for (int k = l; k <= r; k++)
          dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
      }
    }
  }
  if (dp[0][maxlen - 1] == 0)
    cout << "True\n";
  else
    cout << "False\n";
  cout << dp[0][maxlen - 1];
  return 0;
}


目录
相关文章
|
24天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
61 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
26天前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
91 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
28天前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
27 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
28天前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
17 0
|
2月前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
345 8
|
1月前
|
算法
计科一二班算法数据结构实验9答案
计科一二班算法数据结构实验9答案
13 0
|
3月前
|
算法 Java 测试技术
算法分析(蛮力法与减治算法应用实验报告)
这篇文章是关于算法分析的实验报告,介绍了如何使用蛮力法解决背包问题,并通过伪代码和Java代码实现,同时分析了其时间效率;还介绍了基于减治法思想实现的二叉查找树的插入与查找,同样提供了伪代码、Java源代码实现和时间效率分析,最后展示了测试结果截图。
算法分析(蛮力法与减治算法应用实验报告)
|
3月前
|
机器学习/深度学习 算法 Java
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法,包括它们的伪代码描述、Java源代码实现、时间效率分析,并展示了算法的测试用例结果,使读者对贪婪技术及其应用有了更深入的理解。
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
|
3月前
|
算法 Java 测试技术
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
这篇文章介绍了基于动态规划法的三种算法:解决背包问题的递归和自底向上实现、Warshall算法和Floyd算法,并提供了它们的伪代码、Java源代码实现以及时间效率分析。
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
|
4月前
【数据结构OJ题】有效的括号
力扣题目——有效的括号
34 1
【数据结构OJ题】有效的括号