山东大学数据结构与算法实验6栈（计算表达式）实验7队列（卡片游戏）

山东大学数据结构与算法实验6栈（计算表达式）创建栈类，采用数组描述；计算数学表达式的值。输入数学表达式，输出表达式的计算结果。数学表达式由单个数字和运算符+、-、*、/、(、) 构成，例如2+3*(4+5)-6/4。假定表达式输入格式合法实验7队列（卡片游戏）创建队列类，使用数组描述的循环队列，假设桌上有一叠扑克牌，依次编号为 1-n（从上至下）。当至少还有两张的时候，可以进行操作：把第一张牌扔掉

Water_Star1

1584人浏览 · 2024-07-19 15:13:44

Water_Star1 · 2024-07-19 15:13:44 发布

计算表达式

题目描述

创建栈类，采用数组描述；
计算数学表达式的值。
输入数学表达式，输出表达式的计算结果。数学表达式由单个数字和运算符 +、-、*、/、(、) 构成，例如 2+3*(4+5)-6/4。假定表达式输入格式合法

输入输出格式

输入：

第一行一个整数n(1<=n<=100)，代表表达式的个数。

接下来n行，每行一个表达式，保证表达式内的数字为单个整数，表达式内各运算符和数字间没有空格，且表达式的长度不超过2000。

输出：

每行表达式输出一个浮点数，要求保留两位小数，保证输入表达式合法

数据结构与算法描述

设计一个栈类，包括栈是否为空、元素个数、栈顶元素、删除栈顶元素、在栈顶加入元素等成员函数。

template<class T>
class arrayStack {
private:
	int stackTop;//栈顶
	int arrayLength;//栈的容量
	T* stack;//元素数组
public:
	arrayStack(int al=2000) {
		arrayLength = al;
		stack = new T[al];
		stackTop = -1;//栈为空
	}
	~arrayStack() { delete[] stack; }
	bool empty()const { return stackTop == -1; }//判断是否为空
	int Stacksize()const { return stackTop + 1; }//元素个数
	T& top() { return stack[stackTop]; }//返回栈顶元素
	void pop() {//删除栈顶元素
		stack[stackTop] = 0;
		stackTop--;
	}
	void push(const T& theElement) {//在栈顶后加入元素
		++stackTop;
		stack[stackTop] = theElement;
	}
};

生命两个栈一个是数字栈、一个是运算符栈，当是数字字符时压入数字栈。当是左括号时直接压入运算符栈，当运算符栈时空的或者栈顶元素为左括号时直接压入栈中。当输入的运算符优先级比栈顶的高时，直接压入栈中。当输入的运算符优先级与栈顶的一样或者更低时，先将两个数字栈中的前两个数弹出，运算符的栈顶运算符弹出，进行一次计算，然后再进行将输入的运算符与栈顶的运算符优先级比较，直到运算符的栈为空或者栈顶为左括号，或者遇到了优先级比输入运算符低的停止循环。当遇到右括号时也要将两个数字栈中的前两个数弹出，运算符的栈顶运算符弹出，进行一次计算，直到栈顶元素为左括号了，然后删掉这个左括号。

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string x;
		cin >> x;
		int size = x.size();//获取字符串长度
		arrayStack<double> num(size);//数字栈
		arrayStack<char> operators(size);//运算符栈
		for (int i = 0; i <= size; i++) {
			if (x[i] >= '0' && x[i] <= '9') {//如果是数字则压入数字栈
				double a = x[i] - '0';
				num.push(a);
			}
			else {//当是运算符时
				if (x[i] == '(') {//左括号直接插入到栈中
					operators.push(x[i]);
				}
				else {//除左括号的其他运算符
					if (operators.empty() || operators.top() == '(') {//当栈为空或者栈顶为左括号时，该运算符直接插入
						operators.push(x[i]);
					}
					else if (x[i] == ')') {//如果该运算符为右括号
						while (operators.top() != '(') {在出现左括号之前
							double num2 = num.top();
							num.pop();
							double num1 = num.top();
							num.pop();
							char op = operators.top();
							operators.pop();
							if (op == '*') {
								num.push(num1 * num2);
							}
							else if (op == '/') {
								num.push(num1 / num2);
							}
							else if (op == '+') {
								num.push(num1 + num2);
							}
							else if (op == '-') {
								num.push(num1 - num2);
							}
						}
						operators.pop();//删掉左括号
					}
					else {
						if ((x[i] == '*' || x[i] == '/') && (operators.top() == '+' || operators.top() == '-')) {
							operators.push(x[i]);//如果输入的运算符优先级比栈顶的高
						}
						else {//如果输入的运算符优先级与栈顶的一样或者更低
							do {//将依次取出数字栈顶的两个数字.以及运算符栈的一个运算符
								double num2 = num.top();
								num.pop();
								double num1 = num.top();
								num.pop();
								char op = operators.top();
								operators.pop();
								//计算
								if (op == '*') {
									num.push(num1 * num2);
								}
								else if (op == '/') {
									num.push(num1 / num2);
								}
								else if (op == '+') {
									num.push(num1 + num2);
								}
								else if (op == '-') {
									num.push(num1 - num2);
								}
							} while (!operators.empty() && operators.top() != '(' && !((x[i] == '*' || x[i] == '/') && (operators.top() == '+' || operators.top() == '-')));
							//当运算符栈为空时或运算符栈顶为左括号或者栈顶的运算符比当前运算符优先级低时，停止循环
							operators.push(x[i]);//将当前运算符插入栈中
						}
					}
				}
			}
		}
		printf("%.2lf\n", num.top());//输出最后栈顶的元素，要保留两位小数
	}
}

测试结果

完整代码（含注释）

#include <iostream>
#include<cstdio>
using namespace std;
template<class T>
class arrayStack {
private:
	int stackTop;//栈顶
	int arrayLength;//栈的容量
	T* stack;//元素数组
public:
	arrayStack(int al=2000) {
		arrayLength = al;
		stack = new T[al];
		stackTop = -1;//栈为空
	}
	~arrayStack() { delete[] stack; }
	bool empty()const { return stackTop == -1; }//判断是否为空
	int Stacksize()const { return stackTop + 1; }//元素个数
	T& top() { return stack[stackTop]; }//返回栈顶元素
	void pop() {//删除栈顶元素
		stack[stackTop] = 0;
		stackTop--;
	}
	void push(const T& theElement) {//在栈顶后加入元素
		++stackTop;
		stack[stackTop] = theElement;
	}
};

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string x;
		cin >> x;
		int size = x.size();//获取字符串长度
		arrayStack<double> num(size);//数字栈
		arrayStack<char> operators(size);//运算符栈
		for (int i = 0; i <= size; i++) {
			if (x[i] >= '0' && x[i] <= '9') {//如果是数字则压入数字栈
				double a = x[i] - '0';
				num.push(a);
			}
			else {//当是运算符时
				if (x[i] == '(') {//左括号直接插入到栈中
					operators.push(x[i]);
				}
				else {//除左括号的其他运算符
					if (operators.empty() || operators.top() == '(') {//当栈为空或者栈顶为左括号时，该运算符直接插入
						operators.push(x[i]);
					}
					else if (x[i] == ')') {//如果该运算符为右括号
						while (operators.top() != '(') {在出现左括号之前
							double num2 = num.top();
							num.pop();
							double num1 = num.top();
							num.pop();
							char op = operators.top();
							operators.pop();
							if (op == '*') {
								num.push(num1 * num2);
							}
							else if (op == '/') {
								num.push(num1 / num2);
							}
							else if (op == '+') {
								num.push(num1 + num2);
							}
							else if (op == '-') {
								num.push(num1 - num2);
							}
						}
						operators.pop();//删掉左括号
					}
					else {
						if ((x[i] == '*' || x[i] == '/') && (operators.top() == '+' || operators.top() == '-')) {
							operators.push(x[i]);//如果输入的运算符优先级比栈顶的高
						}
						else {//如果输入的运算符优先级与栈顶的一样或者更低
							do {//将依次取出数字栈顶的两个数字.以及运算符栈的一个运算符
								double num2 = num.top();
								num.pop();
								double num1 = num.top();
								num.pop();
								char op = operators.top();
								operators.pop();
								//计算
								if (op == '*') {
									num.push(num1 * num2);
								}
								else if (op == '/') {
									num.push(num1 / num2);
								}
								else if (op == '+') {
									num.push(num1 + num2);
								}
								else if (op == '-') {
									num.push(num1 - num2);
								}
							} while (!operators.empty() && operators.top() != '(' && !((x[i] == '*' || x[i] == '/') && (operators.top() == '+' || operators.top() == '-')));
							//当运算符栈为空时或运算符栈顶为左括号或者栈顶的运算符比当前运算符优先级低时，停止循环
							operators.push(x[i]);//将当前运算符插入栈中
						}
					}
				}
			}
		}
		printf("%.2lf\n", num.top());//输出最后栈顶的元素，要保留两位小数
	}
}

卡片游戏

题目描述

要求

创建队列类，使用数组描述的循环队列
实现卡片游戏

描述

假设桌上有一叠扑克牌，依次编号为 1-n（从上至下）。当至少还有两张的时候，可以进行操作：把第一张牌扔掉，然后把新的第一张（原先扔掉的牌下方的那张牌,即第二张牌）放到整叠牌的最后。输入 n，输出最后剩下的牌。

输入输出格式

输入：

一个整数n，代表一开始卡片的总数。

输出：

最后一张卡片的值。

数据结构与算法描述

创建队列类，用数组秒速的循环队列。私有成员有，第一个数前一个位置的索引queuefront，最后一个数的索引queueback，队列长度，数组。公有成员函数有判断是否为空的empty函数，返回数组中数的个数的函数，返回第一个数的函数，返回最后一个数的函数，删除函数将第一个数前一个位置的索引向后移一位，并将该位置改为0。

插入函数，先判断是否数组空间是否满了，当最后一个数的索引加一后除以数组长度取余和第一个数前一个位置的索引相等时说明满了，将原数组的长度改为原来的2倍，先声明一个长度为原来二倍的新数组，再将原来数组的数从queuefront+1到queueback依次赋给新的数组从0开始一次向后的位置，最后一个数的位置就是新的queueback，新的queuefront = 2 * arraylength – 1，delete掉原来的数组，再将新数组赋给原数组。插入直接在queueback后面的一个位置（因为是环形所以要取余）。

测试结果

完整代码（含注释）

#include<iostream>
using namespace std;
class arrayqueue {
private:
	int queuefront;//第一个数前一个位置的索引
	int queueback;//最后一个数的索引
	int arraylength;//队列长度
	int* queue;
public:
	arrayqueue(int l) {
		arraylength = l;
		queue = new int[arraylength];
		queuefront = queueback = 0;
	}
	~arrayqueue() { delete[] queue; }
	bool empty()const { return queuefront == queueback; }//是否为空
	int size()const { return (arraylength + queueback - queuefront) % arraylength; }//循环列表大小
	int front() { return queue[(queuefront + 1) % arraylength]; }//第一个位置
	int back() { return queue[queueback]; }//最后一个数
	void pop() {//删除
		queuefront = (queuefront + 1) % arraylength;
		queue[queuefront] = 0;
	}
	void push(int theelement) {//插入
		if ((queueback + 1) % arraylength == queuefront) {//当满的时候需要扩充列表大小
			int* queue2= new int[2 * arraylength];
			int i = queuefront + 1;
			int j = 0;
			while (i != queueback) {
				queue2[j] = queue[i];
				i = (i + 1) % arraylength;
				j++;
			}
			queue2[j] = queue[queueback];
			queuefront = 2 * arraylength - 1;
			queueback = j;
			arraylength *= 2;
			delete[] queue;
			queue = queue2;
		}
		queueback = (queueback + 1) % arraylength;
		queue[queueback] = theelement;
	}
};
int main() {
	int n;
	cin >> n;
	arrayqueue a(n);
	for (int i = 1; i <= n; i++) {
		a.push(i);
	}
	while ( a.size()>1 ) {
		a.pop();
		int f = a.front();
		a.pop();
		a.push(f);
	}
	cout << a.back() << endl;
	return 0;
}