C++ 栈实现逆波兰式求解运算式和两栈共享存储空间

桃扇骨 2022-12-21 00:49 157阅读 0赞

**实验二 栈**

**1****．实验目的**

（1）理解栈的定义、特点及与线性表的异同；

（2）熟悉顺序栈的组织方法，栈满、栈空的判断条件及其描述；

（3）掌握栈的基本操作（进栈、退栈等）。

**2****．实验内容**

（1）设计一个算法，将一般算术表达式转化为逆波兰表达式，并求逆波兰表达 式的值。

（2）设计两个栈 S1、S2 都采用顺序栈方式，并且共享一个存储区\[0，MaxLen-1\]， 为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长

的存储方式，如图 2-1 所示。设计一个有关栈的入栈和出栈算法。

![2020111312120329.png][]

**3.  解题思路**

**（****1****）一般算术表达（中缀表达），如****\#3\*(4+2)/2-5\#****，****\#****为表达式界定符，逆波兰** **表达式（后缀表达式），如前述表达的后缀表达式为：****3 4 2 + \* 2 / 5 -****。**

设中缀表达式 的运算符有\+、\-、\*、/、\#五种，运算符的优先级别从高到低为()、\*、/、\+、\-、\#；有 括号先算括号内，再算括号外的，多层括号由内向外

进行。中缀表达式转换为后缀表达式需要用到一个临时栈 OPTR暂存运算符。

**转换算法描述（伪代码）如下：**

1．将栈 OPTR初始化为\#；

2．从左至右依次扫描表达式的每个字符，执行下述操作

2.1 若当前字符是运算对象，则输出该字符，处理下一个字符；

2.2 若当前字符是运算符且优先级别比栈 OPTR的栈顶运算符的优先级 高，则将该字符入栈OPTR，处理下一个字符；

2.3 若当前字符是运算符且优先级别比栈 OPTR的栈顶运算符优先级别 低，则将栈 OPTR的栈顶元素弹出并输出；

2.4 若当前字符是运算符且优先级别与栈OPTR的栈顶运算符的优先级相 等，则将栈 OPTR的栈顶元素弹出，处理下一个字符。

**后缀表达式求值，由于后缀表达中所有的计算按运算符出现的顺序从左向右进****行，不用再考虑运算符的优先级。设定一个临时堆栈 OPND 暂存计算过程的中间结果。**

**后缀表达式计算算法描述（伪代码）如下：**

1．初始化栈 OPND 为空；

2．从左到右依次扫描表达式的每一个字符，执行下述操作；

2.1 若当前是运算对象，则入栈 OPND，处理下一个字符；

2.2 若当前字符是运算符，则从栈 OPND 出栈两个运算对象，执行运算并       将 结果入栈 OPND，处理下一个字符；

3．输出栈 OPND 的栈顶元素，即表达式的运算结果。

**在实现上述要求的算法之前：首先用C++实现栈**

//顺序栈的实现
    #include <iostream>
    using namespace std;//将顺序栈的类定义和各个成员函数定义写到这里 
    const int StackSize = 10;//根据实际问题具体定义
    typedef int DataType;
    class SeqStack
    {
    	public:
    		SeqStack();//构造函数，初始化一个空栈
    		~SeqStack();//析构函数
    		void Push(DataType x);///入栈函数，将元素x入栈
    		DataType Pop();//出栈操作，将栈顶元素弹出
    		DataType GetTop();//取栈顶元素(并不删除)
    		int Empty();//判断栈是否为空
    	private:
    		DataType data[StackSize];//存放栈元素的数组
    		int top;//栈顶元素在数组中的下标	
    };
    
    //构造函数----顺序栈的初始化，初始化一个空的顺序栈只需将栈顶指针top置为-1
    SeqStack::SeqStack()
    {
    	top=-1;
    }
    
    //析构函数----顺序栈的销毁，顺序栈是静态存储分配，在顺序栈变量退出作用域时自动释放顺序栈
    //所占存储单元。因此，顺序栈无需销毁，析构函数为空
    SeqStack::~SeqStack()
    {
    	
    }
    
    void SeqStack::Push(DataType x)
    {
    	if(top==StackSize-1) throw "上溢";
    	data[++top]=x;
    } 
    
    //出栈操作----出栈操作只需取出栈顶元素，然后将栈顶元素位置top减1.出栈操作的成员函数定义如下：
    DataType SeqStack::Pop()
    {
    	DataType x;
    	if(top==-1) throw "下溢";
    	x=data[top--];
    	return x;
    } 
    
    //取栈操作----取栈顶元素只是将top位置的栈顶元素取出并返回，并不修改栈顶位置。
    DataType SeqStack::GetTop()
    {
    	DataType x;
    	if(top!=-1) 
    	{
    		x=data[top];
    		return x;
    	}
    } 
    
    //判断栈是否为空
    int SeqStack::Empty()
    {
    	if(top==-1) return 1;
    	else return 0;
    }
    
    int main()
    {
    	int x;
    	SeqStack S{};//定义顺序栈遍历S
    	cout<<"对15和10执行入栈操作,";
    	S.Push(15);
    	S.Push(10);
    	cout<<"当前栈顶元素为："<<S.GetTop()<<endl;//输出栈顶元素10
    	try
    	{
    		x=S.Pop();
    		cout<<"执行一次出栈操作，删除元素"<<x<<endl;//输出出栈元素10	
    	} catch(char * str){
    		cout<<str<<endl;
    	}
    	try
    	{
    		cout<<"请输入待入栈元素：";
    		cin>>x;
    		S.Push(x);
    	}catch(char * str){
    		cout<<str<<endl;
    	}
    	cout<<"当前栈顶元素为："<<S.GetTop()<<endl;//输出栈顶元素
    	if(S.Empty()==1) cout<<"栈为空"<<endl;
    	else cout<<"栈非空"<<endl;//栈有2个元素，输出栈非空
    	return 0; 
    }

**C++程序：**

**后缀表达式写法：**

**（1）中缀表达式转后缀  
1)如果遇到操作数，我们就直接将其输出。  
2)如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。  
3)如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。  
注意，左括号只弹出并不输出  
4)如果遇到任何其他的操作符，比如是+-\*^/)等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。  
弹出完这些元素后，才将遇到的操作符压入到栈中。  
5)如果我们读到了输入的末尾，则将栈中所有元素依次弹出。**

**（2）后缀表达式运算：**

**1)首先从变量字符串中挑出字符和操作数，操作数有整型数和浮点数。提取整型数和浮点数的思路如下例子：**

**如果当前字符的值落在'0'-'9'之间，例如str"(105+12.68)\*3",**

**①整数提取思路：定义变量和初始化变量, 注意t初始化为1**

**当扫描到1的时候：t=1\*1**

**当扫描到0的时候：t=t\*10+0**

**当扫描到5的时候：t=t\*10+5**

**扫描到字符的值不在'0'-'9'的时候且字符不为小数点：**

**结束整数提取！！！**

**②浮点数提取思路：定义变量和初始化变量, 注意t和e10初始化为1**

**当扫描到1的时候：t=1\*1 **

**当扫描到2的时候：t=t\*10+2**

**当扫描到小数点的时候：****e10=e10\*10;** **t=t+6/e10 ;（注意：t=t+6/e10相当于 t=t+6/10）**

**当扫描到8的时候：****e10=e10\*10;****t=t+8/e10;（注意：t=t+8/e10相当于 t=t+8/100）**

**扫描到字符的值不在'0'-'9'的时候：**

**结束浮点数提取！！！**

**2）实现后缀表达式运算：**

**从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。**

**例如：求中缀表达式：5+（4-6/2）\*3 的值过程为：**

**（1）首先，转化为一个等价的后缀表达式：5，4，6，2，/，-，3，\*，+。**

**（2）从左到右扫描后缀式，读入操作数5，4，6，2，把它们依次压入堆栈S，堆栈的形式如图（a）所示。**

![20201118235956437.png][]

**（3）继续扫描后缀式，读入运算符 / ，弹出栈顶的两个操作数2和6，做除法运算，其结果3压入堆栈S，此时堆栈的形式如图（b）所示。**

![20201118235726918.png][]

**（4）继续扫描后缀式，读入运算符 -，弹出栈顶的两个操作数3和4，做减法运算，其结果1压入堆栈S，此时堆栈的形式如图（c）所示。**

![20201118235752232.png][]

**（5）继续扫描后缀式，读入操作数3，依次压入堆栈S，堆栈的形式如图（d）所示。**

![20201118235807549.png][]

**（6）继续扫描后缀式，读入运算符 \*，弹出栈顶的两个操作数3和1，做乘法运算，其结果3压入堆栈S，此时堆栈的形式如图（e）所示。**

![20201118235827377.png][]

**（7）继续扫描后缀式，读入最后一个运算符 +，弹出栈顶的两个操作数3和5，做加法运算，其结果8压入堆栈S，此时堆栈的形式如图（f）所示。此时，栈顶的数据元素即为表达式的最终的值为8。**

![20201118235846143.png][]

#include <iostream>
    #include <math.h>
    #include <string.h>
    #include<stdlib.h>
    #include<math.h>
    using namespace std;//将顺序栈的类定义和各个成员函数定义写到这里 
    const int StackSize = 100;//根据实际问题具体定义
    typedef char DataType;
    
    class SeqStack
    {
    	public:
    		SeqStack();//构造函数，初始化一个空栈
    		~SeqStack();//析构函数
    		DataType Push(DataType x);///入栈函数，将元素x入栈
    		DataType Pop();//出栈操作，将栈顶元素弹出
    		DataType GetTop();//取栈顶元素(并不删除)
    		int Empty();//判断栈是否为空
    		bool BEmpty();//判断栈是否为空
    	private:
    		DataType data[StackSize];//存放栈元素的数组
    		int top;//栈顶元素在数组中的下标	
    };
    
    //构造函数----顺序栈的初始化，初始化一个空的顺序栈只需将栈顶指针top置为-1
    SeqStack::SeqStack()
    {
    	top=-1;
    }
    
    //析构函数----顺序栈的销毁，顺序栈是静态存储分配，在顺序栈变量退出作用域时自动释放顺序栈
    //所占存储单元。因此，顺序栈无需销毁，析构函数为空
    SeqStack::~SeqStack()
    {
    	
    }
    
    DataType SeqStack::Push(DataType x)
    {
    	if(top==StackSize-1) throw "上溢";
    	data[++top]=x;
    } 
    
    //出栈操作----出栈操作只需取出栈顶元素，然后将栈顶元素位置top减1.出栈操作的成员函数定义如下：
    DataType SeqStack::Pop()
    {
    	DataType x;
    	if(top==-1) throw "下溢";
    	x=data[top--];
    	return x;
    } 
    
    //取栈操作----取栈顶元素只是将top位置的栈顶元素取出并返回，并不修改栈顶位置。
    DataType SeqStack::GetTop()
    {
    	DataType x;
    	if(top!=-1) 
    	{
    		x=data[top];
    		return x;
    	}
    } 
    
    //判断栈是否为空
    int SeqStack::Empty()
    {
    	if(top==-1) return 1;
    	else return 0;
    }
    
    bool SeqStack::BEmpty()
    {
    	if(top==-1) return true;
    	else return false;
    }
    //定义Expression类 
    class Expression
    {
    	public:
    		Expression(string str);//构造函数
    		~Expression();//析构函数
    		int prio(char op);
    		Trans();
    		int isNumber(DataType op);
    		double Calculate();
    		float SVF(char array[]);
    	private:
    		string str; 
    		int num; 
    		DataType result[StackSize]; //保存后缀表达式
    };
    
    Expression::Expression(string str) //接收键盘输入并加上定界符 
    {
    	//this->str = str + "#"; 
    	this->str = str; 
    }
    
    Expression::~Expression()
    {
    	
    }
    
    int Expression::prio(char op) {//给运算符优先级排序
        int priority;
        if (op == '^')
        	priority = 3;
        if (op == '*' || op == '/')
            priority = 2;
        if (op == '+' || op == '-')
            priority = 1;
        if (op == '(')
            priority = 0;
        return priority;
    }
    
    //判断是运算对象还是运算符
    int Expression::isNumber(DataType op){
    	switch(op){
    		case ' ':
    		case '(':
    		case ')':
    		case '+':
    		case '-':
    		case '*':
    		case '/':
    		case '^':
    		case '#': return 0;
    		default : return 1;
    	}
    }
    
    Expression::Trans(){ //引用传递 
    	SeqStack OPTR{};//定义运算符栈
    	//OPTR.Push('#');
    	int i;
    	int j=0;
    	int flag=1;
    	for (i=0; i<str.size(); i++) {
    		//cout<<"str[i]"<<str[i]<<endl;
    		if(isNumber(str[i]))//如果是数据，直接入栈
    		{
    			result[j++] = str[i];
    		}
    		else
    		{//否则不是数字 
    			//cout<<"hello"<<endl;
    			//cout<<"OPTR.Empty()"<<OPTR.Empty()<<endl;
    			result[j++] = ' ';
    			if(OPTR.Empty()||str[i]=='('){//栈空入栈或者左括号入栈 
    				//OPTR.GetTop(); 
    				OPTR.Push(str[i]);
    			}
    			else if(str[i] == ')')
    			{//如果是右括号，只要栈顶不是左括号，就弹出并输出
    				while(OPTR.GetTop()!='(')
    				{
    					result[j++] = ' ';
    					result[j++] = OPTR.GetTop();
    					OPTR.Pop();
    				}
    				OPTR.Pop();//弹出左括号，但不输出 
    			}
    			else
    			{
    				while (prio(str[i]) <= prio(OPTR.GetTop())) { //栈顶优先级大于等于当前运算符，则输出
    					result[j++] = ' ';
    					result[j++] = OPTR.GetTop();
    					OPTR.Pop();
    					if(OPTR.Empty())//栈为空，停止
    					{
    						break; 
    					}
    				}
    				result[j++] = ' ';
    				OPTR.Push(str[i]);//把当前运算符入栈 
    			}
    		}
    	}
    	
    	while(!OPTR.Empty()){//最后，如果栈不空，则弹出所有元素并输出
    		result[j++] = ' ';
    		result[j++] = OPTR.GetTop();
    		OPTR.Pop();
    	}
    	num=j;
    	for(i=0; i<j; i++)
    	{
    		cout<<result[i];
    	}
    	cout<<endl;
    }
    
    float Expression::SVF(char array[])
    {
    	float value;
        /* 需要注意的是，这里没有终结符，故需要知道数组的 */
        /* 大小（数组的大小是编译时常量）*/
        char *dest_str; // 目标字符串
        dest_str = (char *)malloc(sizeof(char) * (sizeof(array) + 1));/* 为字符串分配堆空间 */
        strncpy(dest_str, array, sizeof(array));// 用C标准库函数strncpy拷贝字符
    	value = atof(dest_str);
    	return value;
    }
    
    
    //计算后缀表达式中的值
    double Expression::Calculate(){
    	int i, top=-1;
    	double cal[10] = {0.0};
    	for(i=0; i<num; i++)
    	{
    		if(isNumber(result[i]))
    		{
    			top++;
    			while(result[i] != ' ')
    			{
    				if(result[i] != '.')
    				{
    					cal[top] = cal[top]*10.0 + (result[i++]-48.0);
    				}
    				else
    				{
    					i++;
    					int j=1;
    					while(result[i]!=' ')
    					{
    						j *= 10;
    						cal[top] = cal[top] + (result[i++]-48.0)/j;
    					}
    					
    					//top++;
    				}				
    			}		
    		}
    		else
    		{
    			switch(result[i])
    			{
    				case '+': cal[top-1] = cal[top-1] + cal[top]; cal[top--] = 0; cout<<cal[top]<<' '; break;
    				case '-': cal[top-1] = cal[top-1] - cal[top]; cal[top--] = 0; break;
    				case '*': cal[top-1] = cal[top-1] * cal[top]; cal[top--] = 0; break;
    				case '/': cal[top-1] = cal[top-1] / cal[top]; cal[top--] = 0; break;
    				case '^': cal[top-1] = pow(cal[top-1],cal[top]); cal[top--] = 0; break;
    				default: break;
    			}
    		}
    	}
    	return cal[top];
    }
    
    int main()
    {
    	cout<<"请输入表达式："<<endl;
    	string str;
    	cin>>str; 
    	Expression E{str}; //定义对象变量E
    	E.Trans();
    	cout<<"运算结果为："<<E.Calculate();
    	return 0;
    } 
    //测试字符串
    //string str="(3.0+2.0/2+100)";
    //string str="(2.5*2+1.5+100+1.1+55/11)*2/4-2";
    //string str="(1.0+1.0)+2+3*4+1.0"; //1.0 1 2.5 * 2 / + 2 * 2 *
    //string str="(1.0+1*2.5/2)*2*2";
    //string str = "(2.5*2+1.5+100+1.1+55/11)*2/4-2^3";
    //string str = "2.5*2+1.5+100+1.1+55/11*2/4-2^3";
    //string str="(1.0+2*2.5/2+15)";

**中缀表达式写法：**

#include <iostream>
    using namespace std;//将顺序栈的类定义和各个成员函数定义写到这里 
    const int StackSize = 10;//根据实际问题具体定义
    typedef char DataType;
    
    class SeqStack
    {
    	public:
    		SeqStack();//构造函数，初始化一个空栈
    		~SeqStack();//析构函数
    		void Push(DataType x);///入栈函数，将元素x入栈
    		DataType Pop();//出栈操作，将栈顶元素弹出
    		DataType GetTop();//取栈顶元素(并不删除)
    		int Empty();//判断栈是否为空
    	private:
    		DataType data[StackSize];//存放栈元素的数组
    		int top;//栈顶元素在数组中的下标	
    };
    
    //构造函数----顺序栈的初始化，初始化一个空的顺序栈只需将栈顶指针top置为-1
    SeqStack::SeqStack()
    {
    	top=-1;
    }
    
    //析构函数----顺序栈的销毁，顺序栈是静态存储分配，在顺序栈变量退出作用域时自动释放顺序栈
    //所占存储单元。因此，顺序栈无需销毁，析构函数为空
    SeqStack::~SeqStack()
    {
    	
    }
    
    void SeqStack::Push(DataType x)
    {
    	if(top==StackSize-1) throw "上溢";
    	data[++top]=x;
    } 
    
    //出栈操作----出栈操作只需取出栈顶元素，然后将栈顶元素位置top减1.出栈操作的成员函数定义如下：
    DataType SeqStack::Pop()
    {
    	DataType x;
    	if(top==-1) throw "下溢";
    	x=data[top--];
    	return x;
    } 
    
    //取栈操作----取栈顶元素只是将top位置的栈顶元素取出并返回，并不修改栈顶位置。
    DataType SeqStack::GetTop()
    {
    	DataType x;
    	if(top!=-1) 
    	{
    		x=data[top];
    		return x;
    	}
    } 
    
    //判断栈是否为空
    int SeqStack::Empty()
    {
    	if(top==-1) return 1;
    	else return 0;
    }
    
    //定义Expression类 
    class Expression
    {
    	public:
    		Expression(string str);//构造函数
    		~Expression();//析构函数
    		int Compute();//计算表达式str的值 
    	private:
    		int Comp(char str1,char str2);//比较str1和str2的优先级
    		string str; 
    };
    
    Expression::Expression(string str) //接收键盘输入并加上定界符 
    {
    	this->str = str + "#"; 
    }
    
    Expression::~Expression()
    {
    	
    }
    
    int Expression::Compute()
    {
    	SeqStack OPND{},OPTR{};//定义两个顺序栈 
    	OPTR.Push('#');//栈OPTR初始化为定界符
    	int i, k, x, y, z, op,result;
    	for (i = 0; str[i] != '\0'; ) //依次扫描每一个字符
    	{
    		if (str[i] >= 48 && str[i] <= 57) //数字0的ASCII码是48
    		{
    			//OPND.Push(str[i]-48);
    			//i++;
    			OPND.Push(str[i++]-48);//将字符转换为数字进行压栈 
    		}
    		else  
    		{
    			k = Comp(str[i],OPTR.GetTop());//k=当前字符与运算符栈OPTR的栈顶字符进行对比的结果  
    			//k=1，则当前字符入栈 ； 
    			//k=-1,则栈顶字符出栈，运算对象栈OPND出栈两个操作数，与之进行相应运算,将运算结果入运算对象栈OPND 
    		    //k=0，则栈顶字符出栈;
    			if (k == 1) //str[i]的优先级高
    			{
    				//OPTR.Push(str[i]);
    				//i++;
    				OPTR.Push(str[i++]);//将str[i]压入运算符栈，处理下一个字符 
    			}
    			else if (k == -1) //str[i]的优先级低
    			{
    				y = OPND.Pop();//从运算对象栈出栈两个操作数
    				x = OPND.Pop();
    				op = OPTR.Pop(); //从运算符栈出栈一个运算符
    				switch (op) // op为运算符，进行相应运算
    				{
    					case '+': z = x + y; break;
    					case '-': z = x - y; break;
    					case '*': z = x * y; break;
    					case '/': z = x / y; break;
    					default: break;
    				}
    					OPND.Push(z);//运算结果入运算对象栈
    			}
    			else 
    			{ //str[i]与运算符栈的栈顶元素优先级相同
    				OPTR.Pop(); //将栈OPTR的栈顶运算符出栈
    				i++;//处理下一个字符 
    			}
    		}
    	}
    	result = OPND.Pop();//运算对象栈的栈顶操作数即为运算结果
    	return result; 
    }
    
    //比较str1和str2的优先级，1：str1高；0：相同；-1：str1低
    int Expression :: Comp(char str1, char str2) 
    { 
    	switch (str1)
    	{
    		case '+': case '-': if (str2 == '(' || str2 == '#') return 1; else return -1;
    		break;
    		case '*': case '/': if (str2 == '*' || str2 == '/') return -1; else return 1;
    		break;
    		case '(': return 1; break;
    		case ')': if (str2 == '(') return 0; else return -1;
    		break;
    		case '#': if (str2 == '#') return 0; else return -1;
    		break;
    		default: break;
    	}
    }
    
    int main()
    {
    	string str="1+2/(4-2)+5*3"; //17
    	//string str="1+2/(4-2+2)+5*3"; //16
    	//string str="1+(2/(4-2)+(5*3))"; //17
    	Expression E{str}; //定义对象变量E
    	E.Compute(); 
    	int result = E.Compute( ); //result保存计算结果
    	cout << "表达式的值是："<<str<<" = "<<result << endl;
    	return 0;
    }

**实验结果图：**

![20201119000346161.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70][]

*  **思考：如果表示出现多括号怎么处理**
 *  **解决方法：**
 *  **括号匹配问题  
            算法：Match(str)  
            输入：以字符串str存储的算术表达式  
            输出：匹配结果，0表示匹配，1表示多左括号，-1表示多右括号  
            1. 栈S初始化;  
            2. 循环变量i从0开始依次读取str\[i\],直到字符串str结束；  
               2.1 如果str\[i\]等于'('，则将'('压入栈s;  
               2.2 如果str\[i\]等于')',且栈S非空，则从栈S中弹出一个'('与')'匹配；如果S为空，则多右括号，输出-1  
               2.3 如果S为空，则左右括号匹配，输出0；否则说明多左括号，输出1； **

#include <iostream>
    #include <math.h>
    #include <string.h>
    #include<stdlib.h>
    using namespace std;//将顺序栈的类定义和各个成员函数定义写到这里 
    const int StackSize = 10;//根据实际问题具体定义
    typedef char DataType;
    
    class SeqStack
    {
    	public:
    		SeqStack();//构造函数，初始化一个空栈
    		~SeqStack();//析构函数
    		void Push(DataType x);///入栈函数，将元素x入栈
    		DataType Pop();//出栈操作，将栈顶元素弹出
    		DataType GetTop();//取栈顶元素(并不删除)
    		int Empty();//判断栈是否为空
    		
    	private:
    		DataType data[StackSize];//存放栈元素的数组
    		int top;//栈顶元素在数组中的下标	
    };
    
    //构造函数----顺序栈的初始化，初始化一个空的顺序栈只需将栈顶指针top置为-1
    SeqStack::SeqStack()
    {
    	top=-1;
    }
    
    //析构函数----顺序栈的销毁，顺序栈是静态存储分配，在顺序栈变量退出作用域时自动释放顺序栈
    //所占存储单元。因此，顺序栈无需销毁，析构函数为空
    SeqStack::~SeqStack()
    {
    	
    }
    
    void SeqStack::Push(DataType x)
    {
    	if(top==StackSize-1) throw "上溢";
    	data[++top]=x;
    } 
    
    //出栈操作----出栈操作只需取出栈顶元素，然后将栈顶元素位置top减1.出栈操作的成员函数定义如下：
    DataType SeqStack::Pop()
    {
    	DataType x;
    	if(top==-1) throw "下溢";
    	x=data[top--];
    	return x;
    } 
    
    //取栈操作----取栈顶元素只是将top位置的栈顶元素取出并返回，并不修改栈顶位置。
    DataType SeqStack::GetTop()
    {
    	DataType x;
    	if(top!=-1) 
    	{
    		x=data[top];
    		return x;
    	}
    } 
    
    //判断栈是否为空
    int SeqStack::Empty()
    {
    	if(top==-1) return 1;
    	else return 0;
    }
    
    //定义Macher类
    class Matcher{
    	public:
    		Matcher(string str);
    		~Matcher(){};
    		int match();
    	private:
    		string str;
    }; 
    
    Matcher :: Matcher(string str){
    	this->str = str;
    }
    
    //输出：匹配结果，0表示匹配，1表示多左括号，-1表示多右括号
    int Matcher :: match()
    {
    	SeqStack S{}; /*定义一个字符对象 */
    	int i; /* top为字符对象S的尾指针 */
    	for (i = 0; str[i] != '\0'; i++) /* 依次对str对象的每个字符, str[i]进行处理 */
    	{
    		if (str[i] == ')') 
    		{ /*当前扫描的字符是右括号*/
    			if (!S.Empty()) S.Pop(); /*出栈前判断栈是否为空,若S为非空，从栈S中弹出一个'('与')'匹配；*/ 
    			else return -1;/*若S为空，从多右括号；*/ 
    		}
    		else if (str[i] == '(') /*当前扫描的字符是左括号*/
    			S.Push(str[i]); /*执行入栈操作*/
    	}
    	if (S.Empty()) return 0; /*栈空则括号正确匹配*/
    	else return 1;
    }
    
    //定义Expression类 
    class Expression
    {
    	public:
    		Expression(string str);//构造函数
    		~Expression();//析构函数
    		float Compute();//计算表达式str的值 
    		float SVF(char array[]);
    	private:
    		int Comp(char str1,char str2);//比较str1和str2的优先级
    		string str; 
    };
    
    Expression::Expression(string str) //接收键盘输入并加上定界符 
    {
    	this->str = str + "#"; 
    	//this->str = str ; 
    }
    
    Expression::~Expression()
    {
    	
    }
    
    float Expression::SVF(char array[])
    {
    	float value;
        /* 需要注意的是，这里没有终结符，故需要知道数组的 */
        /* 大小（数组的大小是编译时常量）*/
        char *dest_str; // 目标字符串
        dest_str = (char *)malloc(sizeof(char) * (sizeof(array) + 1));/* 为字符串分配堆空间 */
        strncpy(dest_str, array, sizeof(array));// 用C标准库函数strncpy拷贝字符
    	value = atof(dest_str);
    	return value;
    }
    
    float Expression::Compute()
    {
    	//SeqStack OPND{},OPTR{};//定义两个顺序栈 
    	SeqStack OPTR{};//定义两个顺序栈 
    	OPTR.Push('#');//栈OPTR初始化为定界符
    	float OPND[20];
    	int OPtop=-1;
    	int i, k, op,j,digit,e10,m,g;
    	float x,y,z,result;
    	j=0,g=0;
    	char TempStr[10];
    	for (i = 0; str[i] != '\0'; i++){
    		if ((str[i]>= '0') && (str[i] <= '9') )
    			j++;
    		else
    		{
    			if(str[i] == '.') 
    			{
    				i=i+1;
    				j=j+1;
    				while((str[i] >= '0') && (str[i] <= '9')){
    					j++;
    					i++;
    				}	
    				if (j > 0){
    					for(k=0;k<j;k++)
    					{
    						TempStr[k]=str[i-j+k];
    					}
    					float value;
    					value = SVF(TempStr);
    					memset(TempStr, 0, sizeof TempStr); //清空数组               
    					cout<<"当前的小数值："<<value<<endl;
    					//OPND.Push(value);
    					OPND[++OPtop]=value;
    					j=0;
    				}
    			}
    			else
    			{
    				if (j > 0){
    					digit = str[i-1]- 48;
    					for (k = 1; k < j; k++){ 
    						e10 = 1;
    						for (m = 1; m <= k; m++)
    							e10 = e10 * 10;
    						digit = digit + (str[i-1-k] - 48)*e10;
    					}
    					cout<<"当前的整数值："<<digit<<endl;
    					//OPND.Push(digit);
    					OPND[++OPtop]=digit;
    					j = 0;
    				}
    			}
    		}
    		if(!((str[i]>= '0') && (str[i] <= '9'))){
    			k = Comp(str[i],OPTR.GetTop());//k=当前字符与运算符栈OPTR的栈顶字符进行对比的结果  
    			cout<<"当前的字符:"<<str[i]<<endl;
    			cout<<"当前字符与运算符栈OPTR的栈顶字符进行对比的结果 :"<<k<<endl;
    			if (k == 1) //str[i]的优先级高
    			{
    				OPTR.Push(str[i]);//将str[i]压入运算符栈，处理下一个字符 
    			}
    			else if (k == -1) //str[i]的优先级低
    			{
    				y=OPND[OPtop--];
    				x=OPND[OPtop--];
    				op = OPTR.Pop(); //从运算符栈出栈一个运算符
    				cout<<"y 的值得："<<y<<endl;
    				cout<<"x 的值得："<<x<<endl;
    				cout<<"当前的op："<<(char)op<<endl;
    				switch (op) // op为运算符，进行相应运算
    				{
    					case '+': z = x + y; break;
    					case '-': z = x - y; break;
    					case '*': z = x * y; break;
    					case '/': z = x / y; break;
    					case '^': z = pow(x,y); break;
    					default: break;
    				}
    				OPND[++OPtop]=z;
    				//OPTR.Push(str[i]);
    				i--;
    				//cout<<"当前的字符 ~~~~~~~:"<<OPTR.GetTop()<<endl;
    			}
    			else 
    			{ //str[i]与运算符栈的栈顶元素优先级相同
    				OPTR.Pop(); //将栈OPTR的栈顶运算符出栈
    			}
    		}
    	}
    	
    	//result = OPND.Pop();//运算对象栈的栈顶操作数即为运算结果
    	result = OPND[OPtop];
    	return result; 
    }
    
    
    //比较str1和str2的优先级，1：str1高；0：相同；-1：str1低
    int Expression :: Comp(char str1, char str2) 
    { 
    	switch (str1)
    	{
    		case '+': case '-': if (str2 == '(' || str2 == '#') return 1; else return -1;
    		break;
    		case '*': case '/': if (str2 == '*' || str2 == '/' || str2 == '^') return -1; else return 1;
    		break;
    		case '^': return 1; break;
    		case '(': return 1; break;
    		case ')': if (str2 == '(') return 0; else return -1;
    		break;
    		case '#': if (str2 == '#') return 0; else return -1;
    		break;
    		default: break;
    	}
    }
    
    int main()
    {
    	cout<<"请输入表达式："<<endl;
    	string str;
    	cin>>str; 
    	cout<<str<<endl;
    	int k; //k接收调用函数Match的结果
    	Matcher M{str};
    	k = M.match( ); //函数调用，实参为字符数组的首地址
    	if (k == 0)
    	{
    		cout << "正确匹配\n";
    		Expression E{str}; //定义对象变量E
    		E.Compute(); 
    		float result = E.Compute( ); //result保存计算结果
    		cout << "表达式的值是："<<str<<" = "<<result << endl;
    	}
    	else if (k == 1)
    		cout << "多左括号\n";
    	else
    		cout << "多右括号\n";
    	return 0;
    } 
    //测试数据
    //string str="1+2/(4-2)+5*3"; //17
    //string str="2^2";
    //string str="(2^2+3)*2";
    //string str="2*(2*2^2+3)";
    //string str="2.0*(2^2*3.0+3)+4.5";//string str="2*(2*2^2+3)";
    //string str="(1.0+2.0+1)";
    //string str="(1.0+100/2+(2.5*10+20)*3.3)";
    //string str="(1+2+2.0)";
    //string str="(1.5+2.5+10)";
    //string str="(1+2-3*2+6)";
    //string str="(3*2+6+15)";
    //string str="(2.5*2+1.5+100)";
    //string str="(2.5*2+1.5+100+1.1+55/11+2^2)*2/4-2";
    //string str="(2.0+2.0)";

**核心代码：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1][]

**（****2****）****两栈共享存储空间**，需要解决的关键问题在于**如何判断栈满和栈空**，由于两栈共享存储空间,入栈和出栈的时候还需要区分是哪个栈。设lsTop是左栈（数组下标为0的一端为栈底）栈顶指针，rsTop 为右栈（数组下标为MaxLen-1 的一端为栈底）栈顶指针。**显然，当两个栈都为空时，****lsTop==1****，****rsTop==MaxLen**，如图 2-2 所示；**当栈满时，****rsTop** **和** **lsTop** **存在以下关系：****rsTop==lsTop+1**，如图 2-3 所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3][]

**C++程序：**

//两栈共享空间的顺序栈C++实现 : 如果需要同时使用具有相同数据类型的两个栈的时候，可以采用一个数组，让一个栈的栈底在该数组的起始端，另一个栈的栈底在数组的结尾，有利于节省空间。
    #include <iostream>
    using namespace std;//将顺序栈的类定义和各个成员函数定义写到这里 
    const int MaxLen = 10;//根据实际问题具体定义
    typedef int DataType;
    class BothSeqStack
    {
    	public:
    		BothSeqStack();//构造函数，初始化一个空栈
    		~BothSeqStack();//析构函数
    		void Push(int s,DataType x);///入栈函数，将元素x入栈
    		DataType Pop(int s);//出栈操作，将栈顶元素弹出
    		DataType GetTop(int s);//取栈顶元素(并不删除)
    		int Empty(int s);//判断栈是否为空
    	private:
    		DataType data[MaxLen];//存放栈元素的数组	
    		int lsTop;//lsTop 是左栈顶指针 
    		int rsTop;//lsTop 是右栈顶指针 
    };
    
    //构造函数----顺序栈的初始化，初始化一个空的顺序栈只需将栈顶指针top置为-1
    BothSeqStack::BothSeqStack()
    {
    	lsTop=-1;
    	rsTop=MaxLen;
    }
    
    //析构函数----顺序栈的销毁，顺序栈是静态存储分配，在顺序栈变量退出作用域时自动释放顺序栈
    //所占存储单元。因此，顺序栈无需销毁，析构函数为空
    BothSeqStack::~BothSeqStack()
    {
    	
    }
    
    //入栈算法：①入左栈: s=1;  ②入右栈: s=2; 且x为入栈元素 
    void BothSeqStack::Push(int s,DataType x)
    {
    	if(rsTop==lsTop+1) throw "栈满";
    	if(s==1)//入左栈
    	{
    		//lsTop++;
    		//data[lsTop]=x;
    		data[++lsTop]=x;
    	}
    	else if(s==2)//入右栈
    	{
    		//rsTop--;
    		//data[rsTop]=x;	
    		data[--rsTop]=x;
    	}
    	else cout<<"该栈不存在！\n"<<endl;
    } 
    
    //出栈算法：①出左栈：s=1; ②出右栈：s=2; 且x为入栈元素  成功返回1 否则返回0 
    DataType BothSeqStack::Pop(int s)
    {
    	/*DataType x;
    	if(top==-1) throw "下溢";
    	x=data[top--];
    	return x;*/
    	DataType x;
    	if(s==1)//出左栈 
    	{
    		if(lsTop==-1) throw "栈已空！\n";
    		x=data[lsTop--];
    	}
    	else if(s==2)//出右栈 
    	{
    		if(rsTop==MaxLen) throw "栈已空！\n";
    		x=data[rsTop--];
    	}
    	return x;
    } 
    
    //取栈操作----取栈顶元素只是将 lsTop 或 rsTop 位置的栈顶元素取出并返回，并不修改栈顶位置。
    DataType BothSeqStack::GetTop(int s)
    {
    	/*
    	DataType x;
    	if(top!=-1) 
    	{
    		x=data[top];
    		return x;
    	}*/
    	DataType x;
    	if(s==1)//左栈 
    	{
    		if(lsTop==-1) throw "栈已空！\n";
    		else x=data[lsTop];
    	}
    	else if(s==2)//右栈 
    	{
    		if(rsTop==MaxLen) throw "栈已空！\n";
    		else x=data[rsTop];
    	}
    	return x;
    } 
    
    //判断栈是否为空
    int BothSeqStack::Empty(int s)
    {
    	/*if(top==-1) return 1;
    	else return 0;*/
    	if(s==1)//左栈 
    	{
    		if(lsTop==-1) return 1;
    		else return 0;
    	}
    	else if(s==2)//右栈 
    	{
    		if(rsTop==MaxLen) return 1;
    		else return 0;
    	}
    }
    
    int main()
    {
    	int x;
    	BothSeqStack S{};//定义顺序栈遍历S
    	S.Push(1,4);
    	cout<<S.GetTop(1)<<endl;
    	S.Push(1,5);
    	cout<<S.GetTop(1)<<endl;
    	S.Push(2,8);
    	cout<<S.GetTop(2)<<endl;
    	S.Push(2,9);
    	cout<<S.GetTop(2)<<endl;
    	return 0;
    }

**实验结果图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4][]

[2020111312120329.png]: /images/20221120/99872676d4a2469a8fc0e1a0ec8a3dbb.png
[20201118235956437.png]: /images/20221120/315bd7c85c204814bedda8c93172d1c6.png
[20201118235726918.png]: /images/20221120/7f5d83e65577486ba0341551ee8a0987.png
[20201118235752232.png]: /images/20221120/221b6841c9a54d61ab1849a8480b3908.png
[20201118235807549.png]: /images/20221120/48ae0f41734d448da4c380ec26738e31.png
[20201118235827377.png]: /images/20221120/ca69f644d95748849b0258298b6f91af.png
[20201118235846143.png]: /images/20221120/dbce6d920417425faf540bd143a9cebf.png
[20201119000346161.png]: /images/20221120/fc824ea356a34e6e90c395fb8506655a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70]: /images/20221120/9a99f3e3936d4d6795d95ff157a6f492.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1]: /images/20221120/50667b0cf9ba4f0bb232c2fb901f6439.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2]: /images/20221120/c7e3cb94054a46a1910acc3a76191785.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3]: /images/20221120/842d2dd4dbfe4dfaa5d6a47fd4ba6e9e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4]: /images/20221120/64feed93949d41a0a529c8b64432d37e.png