中山大学数据结构与算法实验报告1
|
219
|
0
|
学习笔记,实验报告,数据结构与算法

3012 字
|
18 分钟

第一题 Bracket Matching

1.实验题目

2.实验目的

本实验的主要目的是实现括号匹配的检查程序，以验证输入字符串中的括号是否成对匹配。通过本实验，学生能够：

  1. 理解括号匹配问题的重要性及其在编程中的应用场景。
  2. 学习如何使用栈这一数据结构来解决括号匹配问题。
  3. 提高对算法设计和实现的能力，熟悉字符串处理的基本技巧。

3.算法设计

为实现括号匹配的功能，我们采用栈结构来管理括号。具体的算法步骤如下：

  1. 输入处理:
    • 接收一个字符串，该字符串的长度不超过100个字符。
    • 字符串中可能包含字母、数字和各种括号（(, ), {, }, [, ]）。
  2. 栈的使用:
    • 使用一个栈来存储遇到的左括号。
    • 初始化栈为空。
  3. 遍历输入字符串：
    • 处理左括号：
      • 当遇到左括号（(, {, [）时，将对应的右括号（), }, ]）压入栈中。
    • 处理右括号：
      • 当遇到右括号时，检查栈是否为空：
      • 如果栈为空，说明没有对应的左括号，返回“否”。
      • 如果栈不为空，比较栈顶的左括号与当前的右括号是否匹配。如果不匹配，返回“否”。匹配则将栈顶元素弹出。
    • 处理其他字符：
      • 对于其他字符（如字母和数字），直接跳过，不做处理。
  4. 输出处理:
    • 遍历结束后，检查栈是否为空。如果为空，说明所有括号都匹配；如果不为空，说明有未匹配的左括号。
  5. 程序结构：
    • 将转换逻辑封装在一个函数中，主函数用于处理输入输出，使程序结构清晰易懂。
  6. 复杂度分析:
    • 时间复杂度为O(n)，其中n为字符串的长度，因为每个字符只被处理一次。
    • 空间复杂度为O(n)，最坏情况下栈中可能存储所有左括号。

4.程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例，包括不同结构的字符串：

  • 输入示例： 
    a
2-[(1+2)*2]
(a+b])
{a + [b - (c + d)]}
(a+b)*(c+d)
[({})]

输出示例

  • 对应的输出结果： 
    Yes
Yes
No
Yes
Yes
Yes

程序运行

程序会循环读取输入字符串，进行括号匹配检查，并输出结果。当没有输入时，程序结束。以下是完整的C++代码实现：

#include <iostream>
#include <stack>
using namespace std;

// 检查括号是否匹配的函数
bool match(const string& s) {
    stack<char> st; // 使用栈来存储左括号
    for (char c : s) {
        if (c == '(') st.push(')');
        else if (c == '{') st.push('}');
        else if (c == '[') st.push(']');
        else if (c == ')' || c == '}' || c == ']') {
            if (st.empty() || c != st.top()) return false; // 不匹配或栈为空
            st.pop(); // 匹配成功，弹出栈顶
        }
    }
    return st.empty(); // 如果栈为空，说明匹配成功
}

int main() {
    string line;
    while (cin >> line) { // 循环读取输入
        if (match(line))
            cout << "Yes" << endl; // 输出匹配成功
        else
            cout << "No" << endl; // 输出匹配失败
    }
    return 0;
}

5.实验总结与心得

通过本次实验，我对括号匹配问题有了更深入的理解。在实现过程中，使用栈有效管理了括号的匹配关系，使得程序逻辑清晰、易于维护。

在调试的过程中，我意识到处理边界条件的重要性，例如，当输入字符串为空或只包含右括号时，程序需要能够正确判断并返回相应的结果。同时，我也学习到了如何简化代码，使得逻辑更加紧凑。

这次实验不仅提升了我的编程技能，也让我认识到编写高效、可读性强的代码的重要性。通过不断的实践与反思，我相信自己能在今后的学习中取得更大的进步。

第二题 后缀表达式计算

1.实验题目

2.实验目的

本实验旨在通过实现一个后缀表达式计算器，深入理解栈的基本原理以及后缀表达式的计算方法。具体目标包括：

  1. 理解后缀表达式（逆波兰表示法）的概念和特点。
  2. 学会使用栈数据结构来存储操作数和处理运算符。
  3. 提高编程能力，熟悉C++语言的语法和标准库的应用。
  4. 能够格式化输出结果，以满足特定的输出要求。

3.算法设计

在本实验中，我们将设计一个计算后缀表达式的程序，主要步骤如下：

  1. 输入处理：
    • 接收一条后缀表达式字符串，表达式由小写字母和四种运算符（+、-、*、/）组成。
    • 每个小写字母代表一个正整数：a=1, b=2, ..., z=26。
  2. 栈的使用：
    • 使用一个栈来存储操作数。
    • 遍历后缀表达式中的每个字符：
      • 如果字符是小写字母，计算其对应的整数值并推入栈中。
      • 如果字符是运算符，从栈中弹出两个操作数，进行相应的运算（加、减、乘、除），然后将计算结果压回栈中。
  3. 计算结果：
    • 遍历完成后，栈顶的元素即为最终结果。
    • 为确保输出的格式符合要求，使用iomanip库将结果保留两位小数。
  4. 程序结构：
    • 将计算逻辑封装在一个函数中，主函数用于处理输入输出，保证程序的结构清晰易懂。
  5. 复杂度分析：
    • 时间复杂度：O(n)，其中 n 为输入字符串的长度。因为每个字符仅被处理一次，无论是进行 push 操作还是 pop 操作，时间复杂度都为常数级别。
    • 空间复杂度：O(n)，在最坏情况下，栈中可能存储所有操作数的值（对应的字母），因此栈的最大大小可能达到 n。除了栈之外，使用的额外变量（如 d1, d2, result）所占的空间为常数级，忽略不计。

4.程序运行与测试

测试用例

  • 输入示例： 
    ab+c*
int**py++

输出示例

  • 输出结果： 
    9.00
2561.00

程序运行

程序会循环读取后缀表达式，进行计算，并输出结果。当没有输入时，程序结束。

代码实现

以下是完整的C++代码，按照上述算法设计进行实现并通过测试：

#include <iostream>
#include <stack>
#include <iomanip> 
using namespace std;

double f(const string& exp) {
    stack<double> s;
    for (char ch : exp) {
        if (ch >= 'a' && ch <= 'z') {
            // 将字母转换为对应的整数值
            s.push(ch - 'a' + 1);
        } else {
            double d2 = s.top(); s.pop();  // 弹出栈顶元素作为第二操作数
            double d1 = s.top(); s.pop();  // 弹出次栈顶元素作为第一操作数
            double result; // 存储运算结果
            switch (ch) {
                case '+': result = d1 + d2; break;
                case '-': result = d1 - d2; break;
                case '*': result = d1 * d2; break;
                case '/': result = d1 / d2; break;
                default: break;
            }
            s.push(result); // 将结果压回栈中
        }
    }
    return s.top(); // 返回栈顶元素作为最终结果
}

int main() {
    string exp;
    while (cin >> exp) {
        double result = f(exp); // 调用计算函数
        cout << fixed << setprecision(2) << result << endl; // 格式化输出
    }
    return 0;
}

5.实验总结与心得

通过本次实验，我对后缀表达式的计算方法有了更深刻的理解，特别是如何利用栈来管理操作数和运算符。栈的先进后出特性在处理数学运算时非常有效，使得我们可以按照正确的顺序进行计算。

在编程过程中，我也学会了如何处理输入输出，包括如何格式化结果以满足要求。使用iomanip库不仅提升了输出的可读性，也让我更加熟悉C++标准库的功能。遇到的问题和挑战让我思考了多种解决方案，尤其是在运算符处理时，确保了每个操作数的顺序和正确性。

这次实验增强了我的编程能力，使我在数据结构和算法设计方面有了更大的信心。我意识到编写清晰、结构良好的代码是非常重要的，这将为我今后的编程学习打下良好的基础。我期待在未来的学习中，能够运用这些知识和技能，解决更复杂的问题。

第三题 中缀表达式转后缀表达

1.实验题目

2.实验目的

本实验的主要目的是实现中缀表达式到后缀表达式的转换，深入理解表达式的表示方法以及栈的应用。通过该实验，旨在培养学生对算法设计和实现的能力，熟悉数据结构的使用，并提升编程技能和解决实际问题的能力。

3.算法设计

在本实验中，我们将设计一个将中缀表达式转换为后缀表达式的程序。具体步骤如下：

  1. 输入处理：
    • 接收一个中缀表达式字符串，该字符串只包含操作数（单个字母）、运算符（+、-、*、/）和括号（(、)）。
    • 表达式长度不超过100个字符。
  2. 栈的使用：
    • 使用一个栈来存储运算符和左括号，以确保运算符的优先级和括号的配对。
    • 遍历中缀表达式的每个字符：
      • 如果字符是操作数（字母），直接添加到输出字符串（后缀表达式）。
      • 如果字符是左括号，将其压入栈中。
      • 如果字符是右括号，弹出栈中的运算符直到遇到左括号。
      • 如果字符是运算符，比较其与栈顶运算符的优先级，弹出优先级更高或相等的运算符，然后将当前运算符压入栈中。
  3. 输出处理：
    • 遍历完成后，将栈中剩余的运算符依次弹出并添加到后缀表达式中。
  4. 程序结构：
    • 将转换逻辑封装在一个函数中，主函数用于处理输入输出，使程序结构清晰易懂。
  5. 复杂度分析：
    • 时间复杂度为O(n)：每个字符处理一次。
    • 空间复杂度为O(n)：栈和后缀表达式存储的空间。

4.程序运行与测试

测试用例

  • 输入示例： 
    A+B*C-D-E/F
a+(b-c)*d+e/f

输出示例

  • 输出结果： 
    ABC*+D-EF/-
abc-d*+ef/+

程序运行

程序会循环读取中缀表达式，进行转换，并输出对应的后缀表达式。当没有输入时，程序结束。

代码实现

以下是完整的C++代码，按照上述算法设计进行实现并通过测试：

#include <iostream>
#include <stack>
#include <string>
#include <cctype>

using namespace std;

// 判断字符是否为运算符
bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

// 返回运算符的优先级
int f(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

// 中缀表达式转换为后缀表达式的函数
string InfixToPostfix(const string& infix) {
    stack<char> s; 
    string postfix;   
    for (char c : infix) {
        if (isalpha(c)) {
            postfix += c; // 添加操作数
        }
        else if (c == '(') {
            s.push(c); // 左括号压入栈中
        }
        else if (c == ')') {
            while (!s.empty() && s.top() != '(') {
                postfix += s.top(); // 弹出栈中运算符
                s.pop();
            }
            s.pop(); // 弹出左括号
        }
        else if (isOperator(c)) {
            while (!s.empty() && f(s.top()) >= f(c)) {
                postfix += s.top(); // 弹出优先级高的运算符
                s.pop();
            }
            s.push(c); // 当前运算符压入栈中
        }
    }
    while (!s.empty()) {
        postfix += s.top(); // 弹出栈中剩余运算符
        s.pop();
    }
    return postfix; // 返回后缀表达式
}

int main() {
    string infix;
    while(cin >> infix) {
        string postfix = InfixToPostfix(infix); // 调用转换函数
        cout << postfix << endl; // 输出后缀表达式
    }
    return 0;
}

5.实验总结与心得

通过本次实验，我对中缀表达式与后缀表达式的转换有了更加深入的理解。在实现过程中，使用栈来管理运算符和括号的配对，使得表达式的优先级得以正确处理。这种方法不仅清晰高效，也让我更加熟悉了数据结构的应用。

在程序调试阶段，我学习到如何处理边界条件，比如括号的正确配对和运算符优先级的比较。这些细节在实现过程中极为重要，能够确保转换过程的准确性。

另外，输出格式的处理让我体会到了细节决定成败的重要性，确保结果符合要求是一个好的编程习惯。

这次实验提高了我的编程能力和逻辑思维能力，同时也让我意识到不断测试和优化代码的重要性。期待在未来的学习中，继续运用这些知识解决更复杂的问题。

数据结构栈算法队列
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
栈与队列

							
							

							
树与二叉树

							
							

							
顺序表与链表

							
							

							
回溯算法初步(Ⅰ)

							
							

							
递归函数设计技巧

							
							

							
回溯算法初步(Ⅱ)

							
							

							
数据的表示

							
							

							
CPU设计与结构