逆波兰式栈实现

╰+哭是因爲堅強的太久メ 2022-08-06 01:27 197阅读 0赞

因为做二叉树非递归的前后中遍历，用到栈的方法。xpp说那就干脆把四则运算，逆波兰式 栈的实现做了。

这是参考别人的程序写的，注释比较乱。而且这个是直接实现计算机计算的四则运算，没有将逆波兰的表达式打印出来。今天腰太酸了，明天改一改，把逆波兰式打印出来噻333333.栈还有迷宫算法是不是？？？现在脑子里之前看的非递归遍历都想不起来了我擦

#include "stdafx.h"
    #include "stdio.h"
    #include "stdlib.h"
    #include"string.h"
    
    
    #define MAX_OPE_LEN 10
    #define MAX_STRING_LEN 100
    #define MAX_STACK_LEN 100
    
    //
    typedef struct operater
    {
    	char name;
    	int pior;
    	int opernum;
    }Operater;
    
    
    Operater opStack[MAX_OPE_LEN];
    int opStacktop=-1;//外加一个指示栈顶的数，这也挺奇葩的
    
    double   numStack[MAX_STACK_LEN];
    int numStacktop=-1;
    
    int getPior(char name)
    {
    	if (name=='('||name==')')//注意括号的优先级
    	{	return 0;}
    	if (name=='+'||name=='-')
    	{	return 1;}
    	if(name=='*'||name=='/')
    	{	return 2;}
    	if(name=='!')
    	{	return 3;}
    	exit(1);//其他情况则直接退出
    }
    
    int getopernum(char name)
    {
    	if(name=='+'||name=='-'||name=='*'||name=='/')
    	{	return 2;}
    	if(name=='!')
    	{	return 1;}
    	if(name=='('||name==')')//特别注意括号的操作数为0；
    	{	return 0;}
    	exit(1);
    }
    
    void pushoperater(Operater op)//入栈操作的是一个 运算符
    {
    	if (opStacktop<MAX_OPE_LEN-1 )
    	{opStack[++opStacktop]=op;}
    	else
    	{exit(1);}
    }
    
    Operater popoperater()
    {
    	if(opStacktop!=-1)
    	{return opStack[opStacktop--];}
    	else
    	{exit(1);}
    }
    
    
    void pushnum(double num)
    {
    	if (numStacktop<MAX_STACK_LEN-1)
    	{numStack[++numStacktop]=num;}
    	else
    	{exit(1);}
    }
    
    double popnum()
    {
    	if (numStacktop!=-1)
    	{return numStack[numStacktop--];}
    	else
    	{exit(1);}
    }
    
    //将输入的浮点数字符转化为double
    //这个部分也是难点之一
    
    double getNumfromString(char *s,int *i)//char *s是char类型的字符输入开始
    {
    	static char string[MAX_STRING_LEN];
    	int j=0;
    	while (*s>='0'&&*s<='9')
    	{
    		string[j++]=*s;
    		s++;
    	}
    	if (*s=='.')
    	{
    		string[j++]=*s;
    		s++;
    		while(*s>='0'&&*s<='9')
    		{
    			string[j++]=*s;
    		    s++;
    		}
    
    	}
    	(*i)=(*i)+j;
    	string[j]='\0';//表示字符结束
    	return atof(string);//将这个字符转化为num
    }
    
    double operater2num(Operater op)
    {
    	double num2=popnum();
    	double num1=popnum();
    	if (op.name=='+')
    	{return num1+num2;}
    	if (op.name=='-')
    	{return num1-num2;}
    	if(op.name=='*')
    	{return num1*num2;}
    	if(op.name=='/')
    	{return num1/num2;}
    	{exit(1);}
    }
    //=============这部分也是比较难的，暂时可以不看啊===========
    double operater1num(Operater op)//非操作？为何是这样？？
    {
        double num = popnum();
        if (op.name == '!')
        {
            double result = 1;
            while (num > 1)
            {
                result *= num;
                num--;
            }
            return result;
        }
        exit(1);
    }
    
    double operater(Operater op)
    {
    	if (op.opernum==2)
    	{return operater2num(op);}
    	if (op.opernum==1)
    	{return operater1num(op);}
    	exit(1);
    }
    
    //进入复杂的主函数操作
    int main()
    {
    	char string[MAX_STRING_LEN ];
    	printf("输入中缀运算表达式:\n");
    	scanf("%s",string);//注意scanf的用法，输入到string中。%S表明输入的是字符串啊啊啊啊啊啊，%f,输入的是float型啊啊啊啊，并且没有该死的\n
    
    	Operater op,opTop;//后者为栈顶运算符,这个用来表示操作符到了最底部
    	opTop.name='#';
    	opTop.opernum=0;
    	opTop.pior=0;
    
        pushoperater(opTop);
    
    	int i=0;
    	for(i;string[i]!='\0'&&string[i]!='=';)
    	{
    		if (string[i]>='0'&&string[i]<='9')
    		pushnum(getNumfromString(&string[i],&i));//把从i开始的数字都取完，转成num压入栈
        	else
         	{
    	    	op.name=string[i];
    	    	op.opernum=getopernum(op.name);
    	    	op.pior=getPior(op.name);
    	    	opTop=popoperater();//把操作符的栈顶操作符与 新发现的操作符对比
    
    			if (op.name=='(')
    				{
    					pushoperater(opTop);
    				    pushoperater(op);
    			}
    			else if (op.name==')')
    			{
    				while(opTop.name!='(')//只要没到左括号，将这之间的操作数 与numStack中的Num取出来实行运算，运算结果压入numStack
    
    				{
    					pushnum(operater(opTop));
    					opTop=popoperater();
    				}
    
    			}
    			else
    			{
    				if (opTop.name!='#'&&op.pior<=opTop.pior)
    				{
    					pushnum(operater(opTop));
    					
    				}
    				else
    				{
    					pushoperater(opTop);
    				}
    				pushoperater(op);
    			}
    				
    			i++;//因为操作符是一个一个的字符，上面字符与数字转换的时候，可能不是一个一个的加的
         	}   
    		
       //string已经转换完了，这个时候操作符栈还有剩，则全部取出来操作
    		
           }
           while((opTop = popoperater()).name != '#')
    		{
    			pushnum(operater(opTop));
    			
    		}
    		 printf("%f\n", popnum());
    	     system("pause");
    	return 0;
    }

![20141210231844735][]

[20141210231844735]: /images/20220806/f5fb3bee842f4713abacd7add4b450f3.png