链栈以及中缀表达式转后缀表达式并求值的链栈实现

Dear 丶 2023-07-21 11:08 3阅读 0赞

#  #

### 表达式包括浮点数求值的链栈实现 ###

*  
 *  链栈
 *   *  一般链栈
     *   *  一般链栈的创建
         *  进栈
         *  出栈
     *  多链栈
 *  栈的应用：表达式求值
 *   *  中缀表达式转后缀表达式
     *  后缀表达式求值
     *  完整代码

# 链栈 #

为了便于操作，采用带头结点的单链表实现栈，把链表的头指针作为栈顶指针。  
采用链栈不必预先估计栈的最大容量，只要系统有可用的空间，链栈就不会出现溢出的情况。对于链栈，使用完毕后，应该释放其空间。  
链栈的各种基本操作的实现与单链表的操作类似。链栈分为**一般链栈**和**多链栈**。

## 一般链栈 ##

一般链栈类型如下：

typedef struct Node{
        
    	int data;
    	struct Node *next;
    }Node,*ListStack;

用top为栈顶指针，始终指向头节点。若top->next = NULL，则表示栈空。  
下面介绍一般链栈的几种操作是如何实现的。

### 一般链栈的创建 ###

创建一个栈的头节点，返回指向头节点的指针。

ListStack creatStack () 
    {
        
    	ListStack top = new Node;
    	top->next = NULL;
    	return top;
    }

### 进栈 ###

首先申请空间，如果申请失败，则返回false，表示进栈不成功；否则数据进栈，并返回true，表示进栈成功。**为了方便操作，这里使用头插法，当然也可以使用双向链表的尾插法**

bool push(ListStack top, int x)
    {
        
    	ListStack t = new Node;
    	// 空间申请失败
    	if (t == NULL)
    		return false;
    	t->data = x;
    	t->next = top->next;
    	top->next = t;
    	return true;
    }

### 出栈 ###

首先判断是否为空栈，如果栈空，则返回false，否则出栈，释放空间，并返回true。

bool pop(ListStack top, int *p) //p指向的内存用来保存出栈的元素的值
    {
        
    	ListStack t = top->next;
    	// 如果栈空
    	if (t == NULL)
    		return false;
    	top->next = t->next;
    	*p = t->data;
    	delete t;
    	return true;
    }

## 多链栈 ##

在实际应用中，有时需要同时使用两个以上的栈，采用多个顺序栈来处理很不方便，这时可以采用多链栈来处理。  
多链栈是将多个链栈的栈顶指针放在一个一维指针数组中统一管理，从而实现同时管理和使用多个栈。  
对多链栈的操作主要有进栈和出栈。进栈时要考虑进几号栈，只要申请空间成功，就能入栈；出栈时要考虑是从几号栈出栈，栈是否空，如果栈空，就不能出栈。

# 栈的应用：表达式求值 #

## 中缀表达式转后缀表达式 ##

**【算法思想】**  
规定运算符的优先级，然后开始读表达式序列。  
（1）若读入的是空格，则认为是分隔符，无须处理。  
（2）若读入的是运算数，则直接输出。  
（3）若读入的是左括号，则将其压入堆栈中。  
（4）若读入的是右括号，则表明括号内的中缀表达式已经扫描完毕，将栈顶的运算符弹出并输出，直到遇到左括号。最后左括号也出栈，但不输出。  
（5）当读入的是运算符时：如果栈顶运算符优先级“低于”当前运算符，则当前运算符进栈；否则，将栈顶的运算符弹出并输出，重复这个步骤，直到栈顶运算符优先级“低于”当前运  
算符，最后将该运算符压栈。  
（6）若中缀表达式中的各对象处理完毕，则把堆栈中存留的运算符一一弹出并输出。  
例如：利用堆栈将中缀表达式“2\*(9+6/3-5)+4”转换成后缀表达式“2 9 6 3 / +  
5 - \* 4 +”的过程。  
**【程序实现】**

#include<bits/stdc++.h>
    
    using namespace std;
    typedef struct Node{
        
    	char data;
    	struct Node *next;
    }Node,*ListStack;
    ListStack creatStack () 
    {
        
    	ListStack top = new Node;
    	top->next = NULL;
    	return top;
    }
    bool push1(ListStack top, char x)
    {
        
    	ListStack t = new Node;
    	// 空间申请失败
    	if (t == NULL)
    		return false;
    	t->data = x;
    	t->next = top->next;
    	top->next = t;
    	return true;
    }
    bool pop1(ListStack top, char *p) //p指向的内存用来保存出栈的元素的值
    {
        
    	ListStack t = top->next;
    	// 如果栈空
    	if (t == NULL)
    		return false;
    	top->next = t->next;
    	*p = t->data;
    	delete t;
    	return true;
    }
    //判断栈顶的运算符与当前运算符的优先级
    int jdg(char x, char top)
    {
        
    	map<char,int> a;
    	a['+'] = 1;
    	a['-'] = 1;
    	a['*'] = 2;
    	a['/'] = 2;
    	a['('] = 0;
    	return a[x] - a[top];
    }
    //中缀表达式转后缀表达式
    char *change(char *str)
    {
        
    	char *p = new char[1000];//分配内存
    	int j = 0;
    	char *x = new char;
    	ListStack top = creatStack ();//创建一个空栈
    	for(int i = 0; i < strlen(str); i++)
    	{
        
    		if(str[i] == '(')
    			push1(top,str[i]);
    		else if((str[i] >= '0' && str[i] <= '9') || str[i] == '.')
    			p[j++] = str[i];
    		else if(str[i] == ')') 
    		{
        
    			pop1(top,x);
    			while(*x != '(')
    			{
        
    				p[j++] = ' ';//加空格把不同的数值隔开
    				p[j++] = *x;
    				p[j++] = ' ';
    				pop1(top,x);
    			}
    		}
    		else if(str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
    		{
        
    			while (top->next !=NULL && jdg(str[i],top->next->data) <= 0)
    			{
        
    				pop1(top,x);
    				p[j++] = ' ';
    				p[j++] = *x;
    				p[j++] = ' ';
    			}
    			push1(top,str[i]);
    			p[j++] = ' ';
    		}
    	}
    	while (top->next)
    	{
        
    		pop1(top,x);
    		p[j++] = ' ';
    		p[j++] = *x;
    		p[j++] = ' ';
    	}
    	p[j] = '\0';
    	return p;
    }
    int main() {
        
    	// char p[50];//临时保存数值的各个位数
    	char str[1000];
    	scanf("%s",str);
    	char *p = change(str);
    	// printf("%c",*p);
    	printf("%s",p);
    	system("pause");
    }

## 后缀表达式求值 ##

**【算法思想】**  
从左到右读入后缀表达式的各项，并根据读人的对象判断所要执行的操作。 操作分为下面3种情况：  
（1）若读入的是运算数，则将其压入堆栈中。  
（2）若读入的是运算符,则从堆栈中弹出适当数量的运算数并进行计算,然后将计算结果再压回到栈中 。  
（3）处理完整个后缀表达式之后,堆栈栈顶上的元素就是表达式的结果值。  
例如，有一个中缀表达式“（（2+3）\* 8+5+3）\* 6”，其后缀表达式为“6 5 2 3+8\*+3+  
表3.1 所示为利用堆栈对后缀表达式“6 5 2 3+8\*+3+\*”求值的过程。  
下面是c++的实现，[***点击查看python的实现***][python]

//后缀表达式求值
    /*
    输入：6.5 + 6.5 / 2 
    输出：9.75
    */
    double cal(char *str)
    {
        
    	char p[50];//临时保存数值的各个位数
    	int j = 0, index = 0;
    	double a[1000];//顺序栈
    	for(int i = 0; i < strlen(str); i++)
    	{
        
    		if((str[i] >= '0' && str[i] <= '9')||str[i] == '.')
    			p[j++] = str[i];
    		else if(str[i] == ' ' && j)
    		{
        
    			p[j] = '\0';
    			a[index++] = atof(p);
    			j = 0;
    		}
    		else if(str[i] == '*' || str[i] == '/' || str[i] == '-' || str[i] == '+')
    		{
        
    			if(index)
    			{
        
    				switch(str[i])
    				{
        
    					case '+':a[index-2] += a[index-1];break;
    					case '-':a[index-2] -= a[index-1];break;
    					case '*':a[index-2] *= a[index-1];break;
    					case '/':a[index-2] /= a[index-1];break;
    				}
    				index--;
    			}
    		}
    	}
    	return a[0];
    }

## 完整代码 ##

#include<bits/stdc++.h>
    using namespace std;
    typedef struct Node{
        
    	char data;
    	struct Node *next;
    }Node,*ListStack;
    ListStack creatStack () 
    {
        
    	ListStack top = new Node;
    	top->next = NULL;
    	return top;
    }
    bool push1(ListStack top, char x)
    {
        
    	ListStack t = new Node;
    	// 空间申请失败
    	if (t == NULL)
    		return false;
    	t->data = x;
    	t->next = top->next;
    	top->next = t;
    	return true;
    }
    bool pop1(ListStack top, char *p) //p指向的内存用来保存出栈的元素的值
    {
        
    	ListStack t = top->next;
    	// 如果栈空
    	if (t == NULL)
    		return false;
    	top->next = t->next;
    	*p = t->data;
    	delete t;
    	return true;
    }
    //判断栈顶的运算符与当前运算符的优先级
    int jdg(char x, char top)
    {
        
    	map<char,int> a;
    	a['+'] = 1;
    	a['-'] = 1;
    	a['*'] = 2;
    	a['/'] = 2;
    	a['('] = 0;
    	return a[x] - a[top];
    }
    //中缀表达式转后缀表达式
    char *change(char *str)
    {
        
    	char *p = new char[1000];//分配内存
    	int j = 0;
    	char *x = new char;
    	ListStack top = creatStack ();//创建一个空栈
    	for(int i = 0; i < strlen(str); i++)
    	{
        
    		if(str[i] == '(')
    			push1(top,str[i]);
    		else if((str[i] >= '0' && str[i] <= '9') || str[i] == '.')
    			p[j++] = str[i];
    		else if(str[i] == ')') 
    		{
        
    			pop1(top,x);
    			while(*x != '(')
    			{
        
    				p[j++] = ' ';//加空格把不同的数值隔开
    				p[j++] = *x;
    				p[j++] = ' ';
    				pop1(top,x);
    			}
    		}
    		else if(str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
    		{
        
    			while (top->next !=NULL && jdg(str[i],top->next->data) <= 0)
    			{
        
    				pop1(top,x);
    				p[j++] = ' ';
    				p[j++] = *x;
    				p[j++] = ' ';
    			}
    			push1(top,str[i]);
    			p[j++] = ' ';
    		}
    	}
    	while (top->next)
    	{
        
    		pop1(top,x);
    		p[j++] = ' ';
    		p[j++] = *x;
    		p[j++] = ' ';
    	}
    	p[j] = '\0';
    	return p;
    }
    //后缀表达式求值
    double cal(char *str)
    {
        
    	char p[50];//临时保存数值的各个位数
    	int j = 0, index = 0;
    	double a[1000];//顺序栈
    	// 1.6 9 + 5 * 
    	for(int i = 0; i < strlen(str); i++)
    	{
        
    		if((str[i] >= '0' && str[i] <= '9')||str[i] == '.')
    			p[j++] = str[i];
    		else if(str[i] == ' ' && j)
    		{
        
    			p[j] = '\0';
    			a[index++] = atof(p);
    			j = 0;
    		}
    		else if(str[i] == '*' || str[i] == '/' || str[i] == '-' || str[i] == '+')
    		{
        
    			if(index)
    			{
        
    				switch(str[i])
    				{
        
    					case '+':a[index-2] += a[index-1];break;
    					case '-':a[index-2] -= a[index-1];break;
    					case '*':a[index-2] *= a[index-1];break;
    					case '/':a[index-2] /= a[index-1];break;
    				}
    				index--;
    			}
    		}
    	}
    	return a[0];
    }
    int main() 
    {
        
    	char str[1000];
    	scanf("%s",str);
    	char *p = change(str);
    	printf("%s\n",p);
    	printf("%.2f",cal(p));
    	system("pause");
    }

[python]: https://blog.csdn.net/p1967914901/article/details/105322889