数据结构作业之栈

栈的定义

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

基础栈一，结构体和宏

#include 
#include 

#define STACK_MAX_SIZE 10


typedef struct CharStack{
 	int top;
 	
 	int data[STACK_MAX_SIZE];
 } *CharStackPtr;

二，输出栈

void outputStack(CharStackPtr paraStack){
	for(int i = 0; i<= paraStack->top; i++){
 		printf("%c ", paraStack->data[i]);	
	}
	printf("rn");
}

三，初始化空栈

CharStackPtr charStackInit(){
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStackPtr));
	resultPtr->top = -1;
	
	return resultPtr;  
}

四，将数据压入，出栈

void push(CharStackPtr paraStackPtr, int paraValue){
	// Step 1. 检查空间
	if(paraStackPtr->top >= STACK_MAX_SIZE - 1){
		printf("Cannot push element: stack full.rn");
		return;
	}
	
	// Step 2. 更新栈top数据
	paraStackPtr->top++;
	
	// Step 3. 插入元素
	paraStackPtr->data[paraStackPtr->top] = paraValue; 
}


char pop(CharStackPtr paraStackPtr){
	// Step 1. 检查空间
	if(paraStackPtr->top < 0){
		printf("Cannot pop element: stack empty.rn");
		return '';
	}
	
	// Step 2. 更新栈top数据
	paraStackPtr->top--;
	
	// Step 3. 删除元素
	return paraStackPtr->data[paraStackPtr->top+1]; 
}

五，功能测试和程序入口

void pushPopTest(){
	printf("---- pushPopTest begins. ----rn");
	
	// 初始化
	CharStackPtr tempStack = charStackInit();
	printf("After initialization, the stack is: ");
	outputStack(tempStack);
	
	// 栈的插入
	for( char ch = 'a'; ch < 'm'; ch++){
		printf("Pushing %c.rn", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}
			
	// 栈的删除
	for( int i = 0; i < 3; i ++){
		char ch = pop(tempStack);
		printf("Pop %c.rn", ch);
		outputStack(tempStack);
	}  
	
	printf("---- pushPopTest ends. ----rn");
} 

int main(){
	pushPopTest();
	return 0;
}

六，输出结果

---- pushPopTest begins. ----
After initialization, the stack is:
Pushing a.
a
Pushing b.
a b
Pushing c.
a b c
Pushing d.
a b c d
Pushing e.
a b c d e
Pushing f.
a b c d e f
Pushing g.
a b c d e f g
Pushing h.
a b c d e f g h
Pushing i.
a b c d e f g h i
Pushing j.
a b c d e f g h i j
Pushing k.
Cannot push element: stack full.
a b c d e f g h i j
Pushing l.
Cannot push element: stack full.
a b c d e f g h i j
Pop j.
a b c d e f g h i
Pop i.
a b c d e f g h
Pop h.
a b c d e f g
---- pushPopTest ends. ----

栈的应用之括号匹配一，在普通栈的基础上加入判断括号的函数

bool bracketMatching(char* paraString, int paraLength){
	// Step 1. 初始化栈，将'#'放在栈的底部
	CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');
	char tempChar, tempPopedChar;
	
	// Step 2.  顺序判断
	for(int i = 0;i < paraLength; i++){
		tempChar = paraString[i];
		
		switch(tempChar){
			case'(':
			case'[':
			case'{':
				push(tempStack, tempChar);
				break;
			case')':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '('){
					return false;
				}
                break;
			case']':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '['){
					return false;
				}
                break;
			case'}':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '{'){
					return false;
				}
                break;
			default:
				break;
		}
	} 
    tempPopedChar = pop(tempStack);
	if(tempPopedChar != '#'){
		return false;
	}
	return true;
} 


void bracketMatchingTest() {
	char* tempExpression = "[2 + (1 - 3)] * 4";
	bool tempMatch = bracketMatching(tempExpression, 17);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = "( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = ")(";
	tempMatch = bracketMatching(tempExpression, 2);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
}


int main(){
	bracketMatchingTest();
	return 0;
}

此处要注意老师代码的149行是要改成return false,否则特殊情况会出错。

二，输出结果

Is the expression '[2 + (1 - 3)] * 4' bracket matching? 1 
Is the expression '( )  )' bracket matching? 0 
Is the expression '()()(())' bracket matching? 1
Is the expression '({}[])' bracket matching? 1
Is the expression ')(' bracket matching? 0

栈的应用之表达式求值

#include 
#include 
#include 
#include 
#include //优先级判断的头文件

using namespace std;

stack num;//创建储存num的栈
stack op;//创建储存符号的栈

void eval()
{
    auto b = num.top();
    num.pop();
    auto a = num.top();
    num.pop();
    auto c = op.top();
    op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;//因为是先pop的b，所以此处是a/b
    num.push(x);
}

int main()
{
    unordered_map pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};//用于优先级的判断
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ )
    {
        auto c = str[i];
        if (isdigit(c))//isdigit判断c是否是十进制数
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++ ] - '0';//将多位数字和为int数据存储
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        else if (c == ')')
        {
            while (op.top() != '(') eval();//在遇到左括号之前进行从后往前的运算
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();//优先级判断先进行哪种计算
            op.push(c);
        }
    }
    while (op.size()) eval();//如果括号外还有数字，继续进行计算
    cout << num.top() << endl;
    return 0;
}

在学长的代码基础上进行了进一步的讲解与理解，通过c++来写表达式求解可以更加简洁，但是本版本代码还有一些问题，比如不能计算更加复杂的函数以及不能判断输入的表达式是否正确。

模仿着写的c代码

#include 
#include 
#include 
int a[21],b[21],x,num1,num2,len,c[10]={0,0,2,1,0,1,0,2};
void eval(int o)
{
	o=b[o];
	int i,j,k;
	k=0;
	i=a[num1];
	num1--;
	j=a[num1];
	num1--;
	if(o==2)
	{
		k=i*j;
	}
	if(o==3)
	{
		k=i+j;
	}
	if(o==5)
	{
		k=j-i;
	}
	if(o==7)
	{
		k=j/i;
	}
	num1++;
	a[num1]=k;
}
void Test(char* str)
{
	int i,j,k;
	num1=0;num2=0;
	len=(int)strlen(str);
	for(i=0;i='0')
		{
			x=0;
			j=i;
			num1++;
			while(str[j]<='9'&&str[j]>='0'&&j=c[str[i]-40]&&b[num2]!=0)
			{
				eval(num2);
				num2--;
			}
			num2++;
			b[num2]=str[i]-40;
		}
	}
	while(num2!=0)
	{
		eval(num2);
		num2--;
	}
	printf("%dn",a[1]);
}
int main()
{
	char* str1 = "(0+72)/9+1";
    char* str2 = "2+(2+3)/5+1*9";
    Test(str1);
    Test(str2);
    return 0;
}

测试结果：

9
12

完整代码

#include 
#include 

#define STACK_MAX_SIZE 10


typedef struct CharStack{
 	int top;
 	
 	int data[STACK_MAX_SIZE];
 } *CharStackPtr;


void outputStack(CharStackPtr paraStack){
	for(int i = 0; i<= paraStack->top; i++){
 		printf("%c ", paraStack->data[i]);	
	}
	printf("rn");
} 

CharStackPtr charStackInit(){
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStackPtr));
	resultPtr->top = -1;
	
	return resultPtr;  
} 


void push(CharStackPtr paraStackPtr, int paraValue){
	// Step 1. 检查空间
	if(paraStackPtr->top >= STACK_MAX_SIZE - 1){
		printf("Cannot push element: stack full.rn");
		return;
	}
	
	// Step 2. 更新栈top数据
	paraStackPtr->top++;
	
	// Step 3. 插入元素
	paraStackPtr->data[paraStackPtr->top] = paraValue; 
}


char pop(CharStackPtr paraStackPtr){
	// Step 1. 检查空间
	if(paraStackPtr->top < 0){
		printf("Cannot pop element: stack empty.rn");
		return '';
	}
	
	// Step 2. 更新栈top数据
	paraStackPtr->top--;
	
	// Step 3. 删除元素
	return paraStackPtr->data[paraStackPtr->top+1]; 
} 


void pushPopTest(){
	printf("---- pushPopTest begins. ----rn");
	
	// 初始化
	CharStackPtr tempStack = charStackInit();
	printf("After initialization, the stack is: ");
	outputStack(tempStack);
	
	// 栈的插入
	for( char ch = 'a'; ch < 'm'; ch++){
		printf("Pushing %c.rn", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}
			
	// 栈的删除
	for( int i = 0; i < 3; i ++){
		char ch = pop(tempStack);
		printf("Pop %c.rn", ch);
		outputStack(tempStack);
	}  
	
	printf("---- pushPopTest ends. ----rn");
} 

int main(){
	pushPopTest();
	return 0;
}

#include 
#include 
#define true 1
#define false 0
#define bool _Bool
#define STACK_MAX_SIZE 10


typedef struct CharStack{
 	int top;
 	
 	int data[STACK_MAX_SIZE];
 } *CharStackPtr;


void outputStack(CharStackPtr paraStack){
	for(int i = 0; i<= paraStack->top; i++){
 		printf("%c ", paraStack->data[i]);	
	}
	printf("rn");
} 

CharStackPtr charStackInit(){
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(struct CharStack));
	resultPtr->top = -1;
	
	return resultPtr;  
} 


void push(CharStackPtr paraStackPtr, int paraValue){
	// Step 1. 检查空间
	if(paraStackPtr->top >= STACK_MAX_SIZE - 1){
		printf("Cannot push element: stack full.rn");
		return;
	}
	
	// Step 2. 更新栈top数据
	paraStackPtr->top++;
	
	// Step 3. 插入元素
	paraStackPtr->data[paraStackPtr->top] = paraValue; 
}


char pop(CharStackPtr paraStackPtr){
	// Step 1. 检查空间
	if(paraStackPtr->top < 0){
		printf("Cannot pop element: stack empty.rn");
		return '';
	}
	
	// Step 2. 更新栈top数据
	paraStackPtr->top--;
	
	// Step 3. 删除元素
	return paraStackPtr->data[paraStackPtr->top+1]; 
} 


bool bracketMatching(char* paraString, int paraLength){
	// Step 1. 初始化栈，将'#'放在栈的底部
	CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');
	char tempChar, tempPopedChar;
	
	// Step 2.  顺序判断
	for(int i = 0;i < paraLength; i++){
		tempChar = paraString[i];
		
		switch(tempChar){
			case'(':
			case'[':
			case'{':
				push(tempStack, tempChar);
				break;
			case')':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '('){
					return false;
				}
                break;
			case']':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '['){
					return false;
				}
                break;
			case'}':
				tempPopedChar = pop(tempStack);
				if(tempPopedChar != '{'){
					return false;
				}
                break;
			default:
				break;
		}
	} 
    tempPopedChar = pop(tempStack);
	if(tempPopedChar != '#'){
		return false;
	}
	return true;
} 


void bracketMatchingTest() {
	char* tempExpression = "[2 + (1 - 3)] * 4";
	bool tempMatch = bracketMatching(tempExpression, 17);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = "( )  )";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "()()(())";
	tempMatch = bracketMatching(tempExpression, 8);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);

	tempExpression = "({}[])";
	tempMatch = bracketMatching(tempExpression, 6);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);


	tempExpression = ")(";
	tempMatch = bracketMatching(tempExpression, 2);
	printf("Is the expression '%s' bracket matching? %d rn", tempExpression, tempMatch);
}


int main(){
	bracketMatchingTest();
	return 0;
}

数据结构作业之栈

C/C++/C#相关栏目本月热门文章