逆波蘭式 棧實現

逆波蘭式 棧實現

因為做二叉樹非遞歸的前後中遍歷，用到棧的方法。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='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;
}