数据结构实验——实验三--栈实验

一、 实验任务

1.1 顺序栈实验任务

(1)利用顺序栈实现将10进制数转换为x进制数，2<=x<=36，除了阿拉伯数字字符，不够字符使用大写英文字符。要求键盘输入10进制数和转换的目标进制数。比如：37转换为20进制数为1H。

第一组数据：4

第二组数据：311

第三组数据：7254

第四组数据：98357

(2)对一个合法的数学表达式来说，其中的各大小括号“{”，“}”，“[”，“]”，“(”和“)”应是相互匹配的。设计算法对以字符串形式读入的表达式S，判断其中的各括号是否是匹配的。比如：“{[](){}}”是匹配的，“{[(})]”就是不匹配的。

(3)假设栈的输入序列为1、2、3、...、n，设计算法求出所有可能的出栈序列。比如输入1、2、3、4、5，可能出栈的序列为12345、13452等42个。

1.2 链栈实验任务

以带头结点的单链表表示链栈，编写算法实现下列问题的求解。

(1)利用链栈实现将10进制数转换为x进制数，2<=x<=36，除了阿拉伯数字字符，不够字符使用大写英文字符。要求键盘输入10进制数和转换的目标进制数。比如：37转换为20进制数为1H。

第一组数据：4

第二组数据：311

第三组数据：7254

第四组数据：98357

(2)对一个合法的数学表达式来说，其中的各大小括号“{”，“}”，“[”，“]”，“(”和“)”应是相互匹配的。设计算法对以字符串形式读入的表达式S，判断其中的各括号是否是匹配的。比如：“{[](){}}”是匹配的，“{[(})]”就是不匹配的。

(3)假设栈的输入序列为1、2、3、...、n，设计算法求出所有可能的出栈序列。比如输入1、2、3、4、5，可能出栈的序列为12345、13452等42个。

二、栈的扩展实验

非必做内容，有兴趣的同学选做。自行选择栈的存储结构。

1. 假设栈的输入序列为1、2、3、...、n，设计算法实现对给定的一个序列，判定其是否是此栈合法的输出序列。比如输入1、2、3、4、5序列，13452为合法出栈序列；15234是不合法输出序列。
2. 利用栈求解算术表达式的值。

三、算法分析

1. 算法设计

（除书上给出的基本运算（这部分不必给出设计思想），其它实验内容要给出算法设计思想）

(1)“除x取余”方法。设十进制数为N，循环除x，取出 余数，商的整数部分重新赋给N，直至N==0； 再将最后的余数作为x进制数的最高位，第一个余数 作为x进制的最低位，得到x进制数。即：余数逆 （反）序输出。利用栈，每次余数入栈，结束时余数全部出栈即可 得到x进制数。

(2) 括号匹配的四种可能性： ① 左右括号配对次序不正确 ② 右括号多于左括号 ③ 左括号多于右括号 ④ 左右括号匹配正确

顺序扫描算数表达式（表现为一个字符串），当遇到三种类型的左括号时候让该括号进 栈；当扫描到某一种类型的右括号时，比较当前栈顶元素是否与之匹配，若匹配，退栈继续 判断；若当前栈顶元素与当前扫描的括号不匹配，则左右括号配对次序不正确；若字符串当 前为某种类型的右括号而堆栈已经空，则右括号多于左括号；字符串循环扫描结束时，若堆 栈非空（即堆栈尚有某种类型的左括号），则说明左括号多于右括号；否则，括号配对正确。

(3) 每次操作有可能有 2 中操作，要么出栈，要么入栈，且 2 种操作是或的关系。但， 出栈、入栈递归返回后要恢复递归前状态。

1.栈不空，入栈序列中还有数据，出栈递归，入栈递归。

2. 栈不空，入栈序列数据已经处理结束，此时只能选择出栈操作

3. 栈空，入栈序列未处理结束。此时，只能选择入栈操作

(4) “除x取余”方法。设十进制数为N，循环除x，取出 余数，商的整数部分重新赋给N，直至N==0； 再将最后的余数作为x进制数的最高位，第一个余数 作为x进制的最低位，得到x进制数。即：余数逆 （反）序输出。利用栈，每次余数入栈，结束时余数全部出栈即可 得到x进制数。

(5) 括号匹配的四种可能性： ① 左右括号配对次序不正确 ② 右括号多于左括号 ③ 左括号多于右括号 ④ 左右括号匹配正确

顺序扫描算数表达式（表现为一个字符串），当遇到三种类型的左括号时候让该括号进 栈；当扫描到某一种类型的右括号时，比较当前栈顶元素是否与之匹配，若匹配，退栈继续 判断；若当前栈顶元素与当前扫描的括号不匹配，则左右括号配对次序不正确；若字符串当 前为某种类型的右括号而堆栈已经空，则右括号多于左括号；字符串循环扫描结束时，若堆 栈非空（即堆栈尚有某种类型的左括号），则说明左括号多于右括号；否则，括号配对正确。

(6) 每次操作有可能有 2 中操作，要么出栈，要么入栈，且 2 种操作是或的关系。但， 出栈、入栈递归返回后要恢复递归前状态。

1.栈不空，入栈序列中还有数据，出栈递归，入栈递归。

2. 栈不空，入栈序列数据已经处理结束，此时只能选择出栈操作

3. 栈空，入栈序列未处理结束。此时，只能选择入栈操作

每次进出栈的过程，栈中元素和出栈元素初始都在参数中。所以当遇到既能出栈又能进栈的过程时，需要将放在后面函数还原回初始过程的参数。

(7) 用数组 In[]保存入栈序列，Out[]保存输出序列，分别用指针 i，j 指示。用一个 栈模拟进出站的操作。对每个输出元素 Out[j]做如下操作：

1.如果 In[i]< Out[j], 将 In[i]入栈，指针 i 后移，即 i++；

2. 如果 In[i]==Out[j]，2 个指针同时后移，即 i++，j++；

3. 如果栈顶元素==Out[j]，栈顶元素出栈，j 后移，即 j++；

循环结束后，如果栈空，且入栈序列处理完毕，则输出序列是一个合法的出栈序列，否 则不是。

（8）设置2 个栈：操作符栈（oS）和操作数栈（nS）。算法如下：

1．自左往右扫描中缀表达式；

2．如果是操作数，压入操作数栈 nS；

3．如果是算符（包括括号）：

 a）如果栈空，或'('，当前算符直接入算符栈 oS；

b）如果是')'，将算符栈 oS 中'('之前全部算符逐次弹出，对弹出的每个算符，从操作数 栈 nS 弹出 2 个操作数（先弹出的是右操作数，后弹出的是左操作数），进行运算，运算结果 压入操作数栈 nS，最后释放一对括号；

c）其它算符： 如果 oS 栈顶算符优先级大于等于当前算符，弹出栈顶算符，从操作数栈 nS 弹出 2 个操作数（先弹出的是右操作数，后弹出的是左操作数），进行运算，运算结果压入操 作数栈，重复此操作直到栈顶算符优先级低于当前算符。 最后将当前算符压入栈 oS（此时，当前算符优先级高于栈顶算符）。

4．表达式扫描结束，弹出栈中所有剩下算符，每弹出一个算符，都要完成上述相同的操 作数处理。

5．输出操作数栈 nS 中最后剩下的一个操作数即为计算结果。文章来源地址https://www.toymoban.com/news/detail-405696.html

//顺序栈
#include<iostream>
#define MAXLEN 1000
using namespace std;

typedef struct sStack{
	char data[MAXLEN];
	int top;
}seqStack;

bool displayStack(seqStack &S){
	char x;
	if(S.top == -1){
		cout << "栈空！" << endl; 
		return false;
	}else{
		while(S.top >= 0){
			x = S.data[S.top];
			cout << x; 
			S.top--;
		}
		cout << endl;
		return true;
	}
}

seqStack ChangeSystem(int num, int x)//num 为10进制的数字，x是目标的进制数
{  
    seqStack S;
    S.top = -1; 
	while(num != 0)
    {
    	int node = num % x;
        if(node >= 10)
        {
        	S.top++;
            S.data[S.top] = node - 10 + 'A';
        }
        else
        {
            S.top++;
			S.data[S.top] = node + '0';
        }
        num /= x;
    }
    return S;
}
//判断一个数学表达式是否合法
bool bracketMatch2(string str) {
	seqStack S;//定义一个栈
	S.top = -1;
	int len = str.length();//获得数学表达式的长度
	bool tag = true;
	bool result;
	int i = 0;
	char x;
	while (i < len && tag == true) {
		switch  (str[i]) {
		//所有左括号入栈
		case '(':
		case '[':
		case '{':
			if (S.top <= 1000){
				S.top++;
            	S.data[S.top] = str[i];
			}else{
				cout << "栈满！" << endl;
			}
			break;
		case ')':
			//扫描到右括号时，如果当前栈空，右括号多于左括号
			if (S.top == -1) {
				tag = false;
				result = false;
				break;
			}
			//得到栈顶元素，并出栈
			x = S.data[S.top];
			S.top--;
			if(x == '(') {
				break;
			}else {
				tag = false;
				result = false;
				break;
			}
		case ']':
			if (S.top == -1) {
					tag = false;
				result = false;
				break;
			}
			//得到栈顶元素，并出栈
			x = S.data[S.top];
			S.top--;
			if (x == '[') {
				break;
			}
			else {
				tag = false;
				result = false;
				break;
			}
		case '}':
			if (S.top == -1) {
				tag = false;
				result = false;
				break;
			}
			//得到栈顶元素，并出栈
			x = S.data[S.top];
			S.top--;
			if (x == '{') {
				break;
			}
			else {
				tag = false;
				result = false;
				break;
			}
		default:
			break;
		}
		i++;
	}
	if (S.top == -1 && tag == true) {
		result = true;
	}else {
		result = false;
	}
	return result;
}

//void print_valid_sequence(int i,const int n )
// {
//     static int number = 0;//记录序列的个数
//     static seqStack stack;//保存入栈的元素
//     static int array[10];//保存输出的元素
//     int top;//用来取top
//     stack.top = -1;
//     if(i == n+1)//递归结束条件，输出序列
//     {
//         ++number;
//         cout << number << "---";
//         for(int j = 0; j < n - stack.top - 1; ++j)
//            cout << array[j];//正序输出
//         for(int k = stack.top; k >= 0 ; k--)//输出
//         {
//         	cout << stack.data[k];
//		 }
//         cout << endl;
//    }
//    else
//    {
//        stack.top++;
//		stack.data[stack.top] = i;//入栈
//        print_valid_sequence((i+1),n);
//        stack.top--;//为保持stack不变，出栈
// 
//        if(stack.top != -1)//将栈顶元素输出
//        {
//            top = stack.data[stack.top];
//            array[i-stack.top - 2] = top;//将输出的元素放入array中
//            stack.top--;
//            print_valid_sequence(i,n);//i不变
//            stack.top++;
//			stack.data[stack.top] = top;
//        }
//    }
//}

void legalSequence(seqStack S, int In[], int Out[], int len, int i, int j, int &sum) { 
 //In[]入栈序列，也可以用栈来保存，但要注意顺序。 
 //Out[]出栈序列，也可以用栈来保存，但要注意输出循序。
 //len序列长度 
 //i入栈序列元素指针，指示当前处理的入栈序列元素  //j出栈序列元素指针，指示当前获取的出栈序列元素 
 
 //每次操作有可能有2中操作，要么出栈，要么入栈，且2种操作是或的关系。但，出栈、入栈递归返回后要恢复递归前状态 
	//static int sum = 1;
	char x; 
	if(S.top == -1 && j >= len)  //递归出口，获得了一个出栈序列 
    { 
  		            //序列数加1 
  		cout << sum << ": " ;
		for(int i = 0; i < len; i++){//打印序列 
		    cout << Out[i];
		}
		cout << endl;
		sum++;
 	}else if(S.top != -1 && i<len)  //栈不空，入栈序列中还有数据 
 	{ 
      //选择出栈 
  	x = S.data[S.top];
	S.top--;
	Out[j] = x; 
  	j++; 
 	legalSequence(S, In, Out, len, i, j, sum);   
  	j--;  //递归返回，恢复到出栈前的状态 
  	S.top++; 
	S.data[S.top] = x;
      //选择入栈 
	S.top++; 
	S.data[S.top] = In[i];
 	i++; 
 	legalSequence(S, In, Out, len, i, j, sum); 
 	i--;     //恢复到入栈前的状态 
 	S.top--;  
	}else if(S.top != -1 && i>=len)  //栈不空，入栈序列数据已经处理结束 
	{ 
     //此时只能选择出栈操作 
  		x = S.data[S.top];
		S.top--;  
		Out[j]=x; 
  		j++; 
  		legalSequence(S, In, Out, len, i, j, sum); 
  		j--;   //恢复到出栈前状态 
  		S.data[S.top] = x;
		S.top++; 
 	}else if(S.top == -1 && i<len)  //栈空，入栈序列未处理结束 
 	{ 
     //此时，只能选择入栈操作 
  		S.top++;
		S.data[S.top] = In[i];
	  
  		i++; 
  		legalSequence(S, In, Out, len, i, j, sum); 
  		i--;   //恢复到入栈前的状态 
  		S.top--; 
 	}	 
} 

/*用数组 In[]保存入栈序列，Out[]保存输出序列，分别用指针 i，j 指示。用一个
栈模拟进出站的操作。对每个输出元素 Out[j]做如下操作：
如果 In[i]<Out[j]，将 In[i]入栈，指针 i 后移，即 i++；
如果 In[i]==Out[j]，2 个指针同时后移，即 i++，j++；
如果栈顶元素==Out[j]，栈顶元素出栈，j 后移，即 j++；
循环结束后，如果栈空，且入栈序列处理完毕，则输出序列是一个合法的出栈序列，否
则不是。*/
bool legalSequence(int In[], int Out[], int len)
{
	//In[]保存入栈序列
	//Out[]保存输出序列
	int i = 0,j = 0; //i 为入栈序列指针；j 为输出序列指针
	char x;
	seqStack S; //初始化顺序栈
	S.top = -1;
	while(j < len){
		if(S.top >= 0)
			x = S.data[S.top];	
		if(In[i] < Out[j] && i < len) //入栈序列当前元素小于输出序列当前元素
		{
			S.top++;
            S.data[S.top] = In[i]; //输入序列当前元素入栈
			i++; //入栈序列指针后移
		}else if(In[i] == Out[j]) //入栈序列当前元素等于输出序列当前元素
		{
			i++; //指针同时后移	
			j++;
		}else if( x == Out[j]) //栈顶元素等于输出序列当前元素
		{
			S.top--; //出栈
			j++; //输出序列指针后移
		}else
			break;
	}
	if(S.top == -1 && i >= len) //栈空，且入栈序列处理完毕，则输出序列为合法出栈序列，返回 true
		return true;
	else
		return false;
}
/*中缀表达式直接求值需要借助 2 个栈：操作符栈（oS）和操作数栈（nS）。算法如下：
（1）自左往右扫描中缀表达式；
（2）如果是操作数，压入操作数栈 nS；
（3）如果是算符（包括括号）：
 a）如果栈空，或'('，当前算符直接入算符栈 oS；
 b）如果是')'，将算符栈 oS 中'('之前全部算符逐次弹出，对弹出的每个算符，从操作数
栈 nS 弹出 2 个操作数（先弹出的是右操作数，后弹出的是左操作数），进行运算，运算结果
压入操作数栈 nS，最后释放一对括号；
 c）其它算符：
 如果 oS 栈顶算符优先级大于等于当前算符，弹出栈顶算符，从操作数栈 nS 弹出 2
个操作数（先弹出的是右操作数，后弹出的是左操作数），进行运算，运算结果压入操
作数栈，重复此操作直到栈顶算符优先级低于当前算符。
 最后将当前算符压入栈 oS（此时，当前算符优先级高于栈顶算符）。
（4）表达式扫描结束，弹出栈中所有剩下算符，每弹出一个算符，都要完成上述相同的操
作数处理。
（5）输出操作数栈 nS 中最后剩下的一个操作数即为计算结果。*/

double Calculation(double a,double b,char op)          //定义运算 
{
	switch (op) 
	{
	    case '+':
	    	return a + b;
	    	break;
    	case '-':
	    	return a - b;
	    	break;
	    case '*':
	    	return a * b;
	    	break;
	    case '/':
	    	return a / b;
	    	break;
	}
}
 
int Provity(char op)
{
	if(op == '*' || op == '/')
	{
		return 2;
	}
	else if(op == '+' || op == '-') 
	{
		return 1;
	}
	else if(op == '(')
	{
		return 0;
	}
	else if(op == '#')
    {
    	return -1;
	}
	else
	{
		cout << "表达式中含有错误运算符!" << endl;
	}
}
 
double GetNum(int &position, char input[])                           //提取输入的表达式中的数字 
{
	int integer = 0;
	double decimal = 0;
	while (input[position] >= '0' && input[position] <= '9') 
	{
		integer = integer * 10;
		int t;
		t = input[position] - '0';
		integer = integer + t;
		position++;
	}
	if (input[position] =='.') 
	{
		position++;
		int t;
		double w = 0.1;
		while (input[position] >= '0' && input[position] <= '9') 
		{
			t = input[position] - '0';
			decimal = decimal + t * w;
			w = w * 0.1;
			position++;
		}
	}
	return integer + decimal;
}
 
double Compute(int &position, char input[])                                       //计算表达式 
{
	seqStack opstack; 
	opstack.top = 0;                                 //符号栈 
	double numstack[128];                                //数字栈 
	opstack.data[opstack.top] = '#';
    opstack.top++;
    int numtail = 0;
	if (input[0] != '#') 
	{
		cout << "输入公式有误！";
		return -1;
	}
	position = 1; 
	while (input[position] != '#') 
	{           
		if(input[position] == '(')                    	          //当输入'('时
		{
			opstack.data[opstack.top++] = '(';
			position++;
		}
		else if (input[position] == ')') 	           	           //当输入')'时
		{
			position++;
			while (opstack.data[--opstack.top] != '(') 
			{
				double a;
				a = numstack[--numtail];
				double b;
				b = numstack[--numtail];
				char op;
				op = opstack.data[opstack.top];
				if (op =='/' && a == 0) 
				{
					cout << "0不能做除数!\n";
					return -1;
				}
				double result;
				result = Calculation(b, a, op);
				numstack[numtail++] = result;
			}
		}
		else if (input[position] >= '0' && input[position] <= '9') 		//如果是数字
		{
			double num;
			num = GetNum(position, input);
			numstack[numtail++] = num;
		}
		else 		                                                //其它运算符
		{
			while (Provity(input[position]) <= Provity(opstack.data[--opstack.top]) )
			{
				double a;
				a = numstack[--numtail];
				double b;
				b = numstack[--numtail];
				char op;
				op = opstack.data[opstack.top];
				if (op == '/' && a==0) 
				{
					cout << "0不能做除数!\n";
					return -1;
				}
				double result;
				result = Calculation(b, a, op);
				numstack[numtail++] = result;
			}
            opstack.top++;
			opstack.data[opstack.top++] = input[position];
			position++;
		}
	}
	while (opstack.data[--opstack.top] != '#') 
	{
		double a;
		a = numstack[--numtail];
		double b;
		b = numstack[--numtail];
		char op;
		op = opstack.data[opstack.top];
		if (op == '/' && a==0) 
		{
			cout << "0不能做除数!\n";
			return -1;
		}
		double result;
		result = Calculation(b,a,op);
		numstack[numtail++] = result;
	}
	return numstack[--numtail];
} 


//链栈
#include<iostream>
using namespace std;

typedef struct IsNode{
	char data;
	IsNode *next;
}sNode;


bool displayLinked(sNode *& top){
	char x;
	if(top == NULL){
		cout << "栈空！" << endl; 
		return false;
	}else{
		while(top != NULL){
			x = top->data;
			top = top->next;
			cout << x; 
		}
		cout << endl;
		return true;
	}
}

sNode* ChangeSystemLinked(int num, int x)//num 为10进制的数字，x是目标的进制数
{  
    sNode *top;
    top = NULL; 
	while(num != 0)
    {
    	int node = num % x;
        if(node >= 10)
        {
        	sNode *s;
        	s = new sNode;
        	s->data = node - 10 + 'A';
            s->next = top;
            top = s;
        }
        else
        {
            sNode *s;
        	s = new sNode;
        	s->data = node + '0';
            s->next = top;
            top = s;
        }
        num /= x;
    }
    return top;
}

bool bracketMatch2Linked(string str) {
	sNode * u, *top;//定义一个栈
	top = NULL;
	int len = str.length();//获得数学表达式的长度
	bool tag = true;
	bool result;
	int i = 0;
	char x;
	while (i < len && tag == true) {
		switch (str[i]) {
		//所有左括号入栈
		case '(':
		case '[':
		case '{':
			sNode *s;
        	s = new sNode;
        	s->data = str[i];
            s->next = top;
            top = s;
			break;
		case ')':
			//扫描到右括号时，如果当前栈空，右括号多于左括号
			if (top == NULL) {
				tag = false;
				result = false;
				break;
			}
			//得到栈顶元素，并出栈
			x = top->data;
			u = top;
			top = top->next;
			delete u;
			if(x == '(') {
				break;
			}else {
				tag = false;
				result = false;
				break;
			}
		case ']':
			if (top == NULL) {
				tag = false;
				result = false;
				break;
			}
			//得到栈顶元素，并出栈
			x = top->data;
			u = top;
			top = top->next;
			delete u;
			if (x == '[') {
				break;
			}
			else {
				tag = false;
				result = false;
				break;
			}
		case '}':
			if (top == NULL) {
				tag = false;
				result = false;
				break;
			}
			//得到栈顶元素，并出栈
			x = top->data;
			u = top;
			top = top->next;
			delete u;
			if (x == '{') {
				break;
			}
			else {
				tag = false;
				result = false;
				break;
			}
		default:
			break;
		}
		i++;
	}
	if (top == NULL && tag == true) {
		result = true;
	}else {
		result = false;
	}
	return result;
}

void legalSequenceLinked(sNode *top, int In[], int Out[], int len, int i, int j, int &sum) { 
 //In[]入栈序列，也可以用栈来保存，但要注意顺序。 
 //Out[]出栈序列，也可以用栈来保存，但要注意输出循序。
 //len序列长度 
 //i入栈序列元素指针，指示当前处理的入栈序列元素  //j出栈序列元素指针，指示当前获取的出栈序列元素 
 
 //每次操作有可能有2中操作，要么出栈，要么入栈，且2种操作是或的关系。但，出栈、入栈递归返回后要恢复递归前状态 
	//static int sum = 1;
	sNode *u, *s;
	char x; 
	if(top == NULL && j >= len)  //递归出口，获得了一个出栈序列 
    { 
  		            //序列数加1 
  		cout << sum << ": " ;
		for(int i = 0; i < len; i++){//打印序列 
		    cout << Out[i];
		}
		cout << endl;
		sum++;
 	}else if(top != NULL && i<len)  //栈不空，入栈序列中还有数据 
 	{ 
      //选择出栈 
  	x = top->data;
	u = top;
	top = top->next;
	delete u;
	Out[j] = x; 
  	j++; 
 	legalSequenceLinked(top, In, Out, len, i, j, sum);   
  	j--;  //递归返回，恢复到出栈前的状态 
    s = new sNode;  
	s->next = top;
	s->data = x;
    top = s; 
  	
      //选择入栈 
    s = new sNode;
	s->data = In[i];
    s->next = top;
    top = s;
 	i++; 
 	legalSequenceLinked(top, In, Out, len, i, j, sum); 
 	i--;     //恢复到入栈前的状态 
	u = top;
	top = top->next;
	delete u; 
	}else if(top != NULL && i>=len)  //栈不空，入栈序列数据已经处理结束 
	{ 
     //此时只能选择出栈操作 
  		x = top->data;
		u = top;
		top = top->next;
		delete u; 
		Out[j]=x; 
  		j++; 
  		legalSequenceLinked(top, In, Out, len, i, j, sum); 
  		j--;   //恢复到出栈前状态 
      	s = new sNode;
    	s->data = x;
    	s->next = top;
   		top = s;  
 	}else if(top == NULL && i<len)  //栈空，入栈序列未处理结束 
 	{ 
     //此时，只能选择入栈操作 
	    s = new sNode;
		s->data = In[i];
  	    s->next = top;
  		top = s;
  		i++; 
  		legalSequenceLinked(top, In, Out, len, i, j, sum); 
  		i--;   //恢复到入栈前的状态 
		u = top;
		top = top->next;
		delete u;
 	}	 
} 

到了这里，关于数据结构实验——实验三--栈实验的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！