有关栈的问题

tuan_liu

2018-08-19

data-structure

1、利用栈将中缀表达式求值：
计算规则：设两个栈，s1用来存储操作数，s2用来存储运算符。从左往右扫描表达式，遇到操作数就将入栈s1,遇到运算符就入栈s2。
当前扫描到的运算符优先级大于栈顶的运算符的优先级，则入栈，否则，就出栈s1中的两个操作数，进行计算，将计算结果入栈s1。且栈顶的操作数先出栈，放在运算符的右边，栈顶下面的一个操作数后出栈，放在运算符的左边。
如果遇到左括号就直接入栈s2，直到遇到右括号，此时，从栈顶到左括号的运算符都出栈进行计算。出栈的运算符都不再入栈。
如果表达式全部扫描完毕，s2栈中还有运算符的话就挨个出栈进行计算，计算结果依次放入s1栈中。

int getpriority(char op) //判断运算符的优先级
{
	if(op=='+'||op == '-') // 规定只有+,-,*,/这四个运算
		return 0; //若是+，-，则返回0
	else
		return 1; //若是*，/，则返回1
}

int calSub(float opandl,char,op,float opand2,float &result)  //出栈两个操作数和一个运算符进行运算
{
	if(op=='+') result = opandl+opand2;
	if(op=='-') result = opandl-opand2;
	if(op=='*') result = opandl*opand2;
	if(op=='/')
	{
		if(fabs(opand2)<MIN) //判断float型为0的标准语句
		{
			return 0; //除数为0的情况返回0，意为运算失败
		}
		else
		{
			result = opandl / opand2; // 如果除数不是0的话就相除

		}
	}
	return 1;  //成功运算返回1，且结果保存在result中。
}


float calInfix(char exp[]) //计算中缀表达式
{
	float s1[maxSize];int top1=-1; //顺序栈，来存操作数
	char s2[maxSize];int top2=-1;  //存运算符
	int i=0;
	while(exp[i]!='\0') //串尾为\0 
	{
		if('0'<=exp[i] && exp[i]<='9') //这里的0，9都是字符，不是数字，且假设输入都是一位数字
		{                             //所以字符的大小比较，是比较这个字符对应ascll码值
			s1[++top1]=exp[i] -'0'; //exp[i]-'0'就将字符转为这个字符对应的数值，入栈
			++i;                    
		}
		else if (exp[i]=='(')  //如果扫描到了（,则直接入运算符栈
		{
			s2=[++top2]='(';
			++i;
		}
		else if (exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/')  //如果扫描到了运算符
		{                                                             //一般有两种情况，一是直接入栈，二是弹出操作数进行运算后再入栈
			if(top2==-1||s2[top2]=='(' || getpriority(exp[i])>getpriority(s2[top2])) //如果栈空，
                                                                                    //如果为（，                                                          
			{                                                          //如果当前扫描到的运算符的优先级大于栈顶的运算符的优先级
				s2[++top2]=exp[i];  //就入栈
				++i;
			}
			else                           //如果不满足，就弹出运算符，和一些运算符进行运算
			{
				float opnd1,opnd2,result;  //出栈的两个操作数，和结果
				char op;                 //要进行运算的运算符
				int flag;                 //接受calSub返回的标记
				opnd2=s1[top--];   //先出栈的为第二个操作数       
				opnd1=s1[top--];   //后出栈的为第一个操作数，顺序不能弄反了
				op=s2[top2--];     //弹出一个运算符
				flag=calSub(opnd1,op,opnd2,result);  //调用calSub函数，函数返回的是0,1，代表成不成功，结果是存在result中的
				if(flag==0) //0代表计算不成功
				{
					std::cout<<"error"<<std::endl;
					return 0;
				}
				s1[++top1]=result;  //求值成功了就将结果压栈
			}
		}
		else if (exp[i]==')')  //扫描遇到')'时，
		{
			while(s2[top2] !='(')  //就不停的出栈，直到遇到'(',
			{
				float opnd1,opnd2,result;  //且对每一个出栈的运算符进行一次运算
				char op;
				int flag;
				opnd2=s1[top--];
				opnd1=s1[top--];
				op=s2[top2--];
				flag=calSub(opnd1,op,opnd2,result);
				if(flag==0)
				{
					std::cout<<"error"<<std::endl;
					return 0;
				}
				s1[++top1]=result;
			}
			--top2;  //此时指向'(',出栈，去掉他
			++i;  //指向下一个字符
		}
	}
	while(top2!=-1)  //当表达式全部扫描之后，如果栈中还有运算符剩余，就全部出栈，且取两个操作数进行计算
	{
		float opnd1,opnd2,result;
				char op;
				int flag;
				opnd2=s1[top--];
				opnd1=s1[top--];
				op=s2[top2--];
				flag=calSub(opnd1,op,opnd2,result);
				if(flag==0)
				{
					std::cout<<"error"<<std::endl;
					return 0;
				}
				s1[++top1]=result;
	}
	retunr s1[top1]; //操作数的结果在栈顶，返回即可
}

2、用栈求后缀表达式值：
从左往右扫描这个表达式串，当遇到操作数的时候就入栈，当遇到运算符就出栈两个操作数，进行运算，先出栈的操作数放在运算符的左边，后出战的操作数放在运算符的右边。计算出结果，然后将这个结果入栈。一直将运算符全部运算完，最后一个计算结果即所求的值。

float calPostFix(char exp[])
{
	float s[maxsize];int top=-1;
	for(int i=0;exp[i]!='\0';++i)
	{
		if('\0'<=exp[i] && exp[i]<='9')
				s[++top]=exp[i]-'0';
		else //else if (exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/')
		{
			float opnd1,opnd2,result;
			char op;
			int flag;
			opnd2=s[top--];
			opnd1=s[top--];
			op=exp[i];
			flag=calSub(opnd1,op,opnd2,result);
			if(flag==0)
			{
				std::cout<<"error"<<std::endl;
				break;			
			}
			s[++top]=result;
		}
	}
	return s[top];
}

3、用栈求前缀表达式：
从右往左扫描这个表达式。当遇到操作数的时候就入栈，当遇到运算符就出栈两个操作数，进行运算，先出栈的数放在运算符的右边，后出栈的放在运算符的左边。其他操作和后缀表达式计算方式一样。

float calPreFix(char exp[],int len)
{
	float s[maxsize];int top=-1;
	for(int i=len-1;i>=0;--i)  //从右往左
	{
		if('\0'<=exp[i] && exp[i]<='9')
				s[++top]=exp[i]-'0';
		else //else if (exp[i]=='+'||exp[i]=='-'||exp[i]=='*'||exp[i]=='/')
		{
			float opnd1,opnd2,result;
			char op;
			int flag;
			opnd1=s[top--]; //这里的出栈操作数的顺序也不一样
			opnd2=s[top--];
			op=exp[i];
			flag=calSub(opnd1,op,opnd2,result);
			if(flag==0)
			{
				std::cout<<"error"<<std::endl;
				return 0;		
			}
			s[++top]=result;
		}
	}
	return s[top];
}```
这里就可以看出，中缀形式求值明显比用后缀或者前缀来的复杂，所以，这就是为什么计算机中会出现在生活中不会使用到的后缀和前缀形式。就像十进制一样，为人们所习惯，而计算机中普遍使用的是二进制。所以我们也必须为计算机的发展创造出能被计算机所方便使用和接受的规则。

**4、中缀转后缀：**
转化规则：从左到右扫描中缀表达式，如果遇到操作数就直接将其写入结果表达式，（这个结果表达式的书写顺序是从左往右书写）如果遇到运算符就将其入栈。
且如果这个即将入栈的运算符**小于等于**当前栈顶的运算符，则将当前栈顶的运算符出栈，写入当前得到的结果表达式中，**这样一直比较下去**，直到即将入栈的运算符的优先级大于当前栈顶的运算符，此时再将这个即将入栈的运算符入栈。如果栈空，就直接入栈，不需要上述的比较。
如果遇到左括号，就直接入栈，当栈顶元素是左括号的时候，所有扫描到的运算符都入栈。当扫描到右括号的时候，执行一系列的出栈操作。将当前栈顶到左括号的运算符全部出栈，并将其写入结果表达式中，其中出栈的括号直接扔掉，左右括号都不写入结果表达式。一个左括号配一个右括号。
此时如果全部扫描完表达式，栈中还有运算符，则将其全部出栈，写入结果表达式中即可。

```c++
void infixToPostFix(char infix[],char s2[],int &top2)//infix为中缀表达式，s2这个栈用来存储转换后的后缀，top2作为栈顶
{	
	char s1[maxSize];int top1=-1;//再定义一个辅助栈
	int i=0;
	while(infix[i]!='\0')
	{
		if('0'<=infix[i] && infix[i]<='9')
		{
			s2[++top2]=infix[i];
			++i;
		}
		else if(infix[i]='(')
		{
			s1[++top]='(';
			++i;
		}
		else if(infix[i]=='+'||infix[i]=='-'||infix[i]='*'||infix[i]='/')
		{
			if(top1==-1||s1[top1]=='(' || getpriority(exp[i])>getpriority(s1[top1]))
			{
				s1[++top1]=infix[i];
				++i;
			}
			else
				s2[++top2]=s1[top1--]; //否则就从s1中出栈一个运算符入s2栈
		}
		else if(infix[i]==')')
		{
			while (s1[top1]!='(')
				s2[++top2]=s1[top--];
			--top1;  //(出栈
			++i;
		}
	}
	while(top1!=1)
		s2[++top2]=s1[top1--];
}

5、中缀转前缀：
转化规则：
从右往左扫描，书写结果表达式的方向是从右往左写。遇到右括号直接入栈，遇到左括号就将当前栈顶到右括号的运算符出栈。
当前运算符如果小于栈顶的运算符时，则当前栈顶的运算符出栈。
其他的操作和中缀转后缀式一样的。

void infixToPreFix(char infix[],char s2[],int &top2,int len)//infix为中缀表达式，s2这个栈用来存储转换后的后缀，top2作为栈顶
{	
	char s1[maxSize];int top1=-1;//再定义一个辅助栈
	int i=len-1;
	while(i>=0)
	{
		if('0'<=infix[i] && infix[i]<='9')
		{
			s2[++top2]=infix[i];
			--i;  //注意
		}
		else if(infix[i]=')') //注意
		{
			s1[++top]=')';
			--i;  //注意
		}
		else if(infix[i]=='+'||infix[i]=='-'||infix[i]='*'||infix[i]='/')
		{
			if(top1==-1||s1[top1]=='）' || getpriority(exp[i])>=getpriority(s1[top1]))  //注意，为>=，不是>
			{
				s1[++top1]=infix[i];
				--i;  //注意
			}
			else
				s2[++top2]=s1[top1--]; //否则就从s1中出栈一个运算符入s2栈
		}
		else if(infix[i]=='(')  //注意
		{
			while (s1[top1]!=')')  //注意
				s2[++top2]=s1[top--];
			--top1;  //(出栈
			--i;  //注意
		}
	}
	while(top1!=1)
		s2[++top2]=s1[top1--];
}

6、括号匹配问题：

int isMatched(char left,char right)
{
	if(left=='(' && right==')')
		return 1;
	if(left=='[' && right==']')
		return 1;
	if(left=='{' && right=='}')
		return 1;
	else
		return 0;
}

int isParenthesesBalanced(char exp[])
{
	char s[maxSize];int top=-1;
	for(int i=0;exp[i]!='\0';++i)
	{
		if(exp[i]=='('||exp[i]=='['||exp[i]=='{')
			s[++top]=exp[i];
		if(exp[i]==')'||exp[i]==']'||exp[i]=='}')
		{
			if(top==-1)
				return 0; //如果栈空就不匹配，返回0

			char left =s[top--];
			if(isMatched(left,exp[i])==0)
				return 0;
		}

	}
	if(top>-1)
		return 0; // 栈不空，则不匹配
	return 1;  //栈为空，则匹配。返回1
}

7、计算问题：
类似于这类问题，可以用递归去处理，不过递归的实质也是用栈，只是这个栈是系统分配的栈，我们这里是自己定义了一个栈。

int calF(int m)
{
	int cum=1;
	int s[maxSize],top=-1;
	while(m!=0)
	{
		s[++top]=m;
		m /= 3;  //m=m/3

	}
	while(top!=-1)
		cum *=s[top--];
	return cum;
}

8、共享栈：
这样来定义共享栈：(假设共享栈由s1和s2两个栈共享)

1 2	int satck[maxsize]; int top1=-1,top2=maxsize;

可以看到，无非就是在栈尾后面一个位置定义一个top2去指向他，在栈首的前一个位置定义一个top1去指向他。
一般的，为了更好的同一形式，不用定义两个新的量去指向这些位置，而是定义一个数组，数组中有两个值，分别指向这两个位置。即：top[2]={-1,maxsize};就可以了。分别用top[0],top[1]去使用它们。

s1栈为空：top[0]==-1;s2栈为空：top[1]==maxsize;
s1入栈：stack[++top[0]] = x;
s2入栈：stack[–top[1]] = x;
栈满判断：top[0]+1==top[1];

9、用栈来模拟队列：
用两个栈来实现，即要将栈的“先进后出”变为队列的“先进先出”。