houzhui.cpp

文件夹中包括常用的数据结构的算法

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define StackSize  100   

int opch[7][7] = {1, 1, -1, -1, -1, 1, 1,                  // 算符间的优先关系
                  1, 1, -1, -1, -1, 1, 1,
                  1, 1,  1,  1, -1, 1, 1,
                  1, 1,  1,  1, -1, 1, 1,
                 -1,-1, -1, -1, -1, 0, 2,
                  1, 1,  1,  1,  2, 1, 1,
                 -1,-1, -1, -1, -1, 2, 0};

int numOfOptr(char ch)      //返回各种运算符在数组中对应的数组下标
{
    switch (ch)
	{
	    case '+': return 0 ; break;
		case '-': return 1 ; break;
		case '*': return 2 ; break;
		case '/': return 3 ; break;
		case '(': return 4 ; break;
		case ')': return 5 ; break;
		case '#': return 6 ; break;
		default : return (-1);
	};
};

bool precede(char ch1, char ch2)
{
    int i,j;

	if((ch1<=9&&ch1>=0) || (ch2<=9&&ch2>=0)) return false;
	i= numOfOptr(ch1);
	j = numOfOptr(ch2);
	if(opch[i][j] == 1) return true;
	else
	{
	    if(opch[i][j] == -1) return false;
		else 
		{
			printf("optr error\n");
			return false;
		};
	}
}

// 定义栈类型
typedef struct
{   
	char data[StackSize];
    int Top;  
} SeqStack;

void Error(char * message)
{  
	printf("Error: %s\n",message);
};

void InitStack( SeqStack *S) //初始化(置空栈)
{ 
	S->Top=-1;
};

int  EmptyStack(SeqStack *S) //判栈空
{  return  S->Top == -1;  }

int FullStack (SeqStack *S)   // 判栈满
{  return S->Top==StackSize-1; }

void Push (SeqStack *S , char  x) //进栈
{  if(FullStack(S))	 Error("Stack overflow");
    S->data[++S->Top]=x;
}

void Pop(SeqStack *S, char *c) // 出栈(退栈)
{  if (EmptyStack( S) )   
           Error( "Stack underflow");
    *c = S->data[S->Top--];
}

void Pass(char *String, char ch)
{
	char tempString[20];
    tempString[0] = ch;
	tempString[1] = '\0';
    strcat(String, tempString);
}

bool IN(char ch)
{ // 若ch是操作数
    if(ch>='0' && ch <='9') return false;
	else{return true;};
}

bool Gettop(SeqStack *S, char *c)
{
	Pop(S, c);
    Push(S, *c);
    if(*c != '#'){return true; }
	else {return false;}
}

int math(int x1, char ch, int x2)
{
    switch (ch)
	{
	    case '+': return (x1 + x2) ; break;
		case '-': return (x1 - x2); break;
		case '*': return (x1 * x2) ; break;
		case '/': return (x1 / x2) ; break;
		default : return (-1);
	};
}

void transform(char *Suffix, char *exp )
{  //从原表达式求得后缀式
   //s是运算符栈，s栈底预设 ‘#’，OP是运算符集合
	char *p;
	char c;
	SeqStack S;

	InitStack(&S);  
	Push(&S, '#');
	
	p = exp;  
    char	ch = *p;
    while (!EmptyStack(&S)) 
    { 
	

		if (!IN(ch)) // 若ch是操作数   /////////////////////////////////
           Pass( Suffix, ch);      /////////////////////////////////
        else 
		{
		    switch (ch)
			{ 
			    case '(' :  Push(&S, ch); break;
                case ')' :  Pop(&S, &c);
                            while (c!= '(' )
							{ 
								Pass( Suffix, c); 
								Pop(&S, &c) ;
							};
                            break; 
                 default  :	 
                 while((Gettop(&S, &c)) && (precede(c,ch)))
				 { 

					 Pass( Suffix, c);
					 Pop(&S, &c); 
				 };
                 if ( ch!= '#' )  Push(&S, ch); 
                 break;  
			} // switch

		}  // 若ch是运算符
        if ( ch!= '#' ) 
		{
		   p++; 
		   ch = *p; 
		}
        else { Pop(&S, &ch);  Pass(Suffix, ch); }
    } // while
 } // CrtExptree


int  cal(char suffixExp[ ] )
//求后缀式表达式的值
//s是运算数栈，OP是运算符集合
{  
	SeqStack S;
	char x2Ch,x1Ch;
    int x1,x2;

	InitStack(&S); 
    int    i = 0;
    char	ch = suffixExp[0];
    while (ch !='#') 
    {
		if (!IN(ch)) // 若ch是操作数
           Push( &S, ch); 
        else // 若ch是运算符
        { 
			Pop(&S,&x2Ch); 
			Pop(&S, &x1Ch);
			x1=(int)x1Ch-48;
			x2=(int)x2Ch-48;
            Push(&S,((char)math(x1, ch, x2)+48));  //将运算结果转换成字符压入栈 
		}
        i++;  
		ch= suffixExp[i];
    } // while
	Pop(&S, &x1Ch);
	return (int)x1Ch-48;
}




void main()
{
    char Exp[30] = "2*4-(7-8/2)*2#";
    char suffix[30];
    suffix[0]='\0';




	transform(suffix, Exp);
	printf("%s\n", Exp);

	printf("%s\n", suffix);
	printf("****%d******\n",cal(suffix));
}


//2*4+(7-4/2)*3#"
//24*742/-3*+