스 택 으로 표현 식 값 구하 기

이전에 글 에서 표현 식 값 을 구 하 는 것 을 쓴 적 이 있 지만 논리 가 좀 복잡 해서 다시 썼 습 니 다.이 프로그램 은 현재 한 자릿수 내의 가감 곱 하기 만 지원 합 니 다.예전 의 실현 사상 과 달리 접미사 표현 식 사상 을 사용 하고 있 습 니 다.모 르 는 것 은 인터넷 에서 자 료 를 찾 아 볼 수 있 습 니 다.이런 사상 은 더욱 이해 하기 쉽다 고 생각한다.
이 프로그램 을 통 해 저 는 많은 것 을 얻 었 습 니 다.두 개의 스 택 을 만들어 야 하기 때문에 하 나 는 데이터 스 택 이 고 다른 하 나 는 문자 스 택 입 니 다.
방안 1:사상 은 우리 가 한 자릿수 이내 의 가감 승제 만 지원 하기 때문에 조작 수 에 대해 문자 로 표시 할 수 있 고 데이터 스 택 에 대해 서도 문자 스 택 으로 표시 할 수 있다 는 것 이다.
방안 2:두 개의 스 택 을 쓰 고 코드 를 모두 복사 한 다음 에 수정 해 야 합 니 다.이렇게 반복 코드 가 높 습 니 다.이것 은 바로 다 중 사상 을 도입 한 것 입 니 다.C+/자바 에 다 중 범 형 이 있 지만 C 에 없 으 면 C 로 다 중 을 실현 할 수 있 습 니 다.한 방안 은 함수 지침 이 고 다른 방안 은 매크로 를 사용 하 는 것 입 니 다.이 프로그램 은 매크로 를 사용 하여 다 중 태 를 실현 합 니 다.

#ifndef STACK_ELEMENT_TYPE
#error "      ，     STACK_ELEMENT_TYPE"
#endif

#ifndef STACK_TYPE
#error "      ，     STACK_TYPE"
#endif

#include 

typedef struct
{
    STACK_ELEMENT_TYPE* elements;
    int top;
    int max;
} STACK_TYPE;

int temp;
/*   ：
 * 1.       ，   #ifndef  ，            ，             
 * 2. C   malloc    void*，       (stack)->elements。  C++  ，  C++         。
 *    C++   STACK_INIT                 ，     。C++       。
 **/
#ifndef STACK_INIT
#define STACK_INIT(stack, maxSize) \
    ((stack).elements = malloc(maxSize * sizeof(((stack).elements)[0])), (stack).top = 0, (stack).max = maxSize)
#endif

#ifndef STACK_DESTROY
#define STACK_DESTROY(stack) \
    (free((stack).elements), (stack).elements = NULL, (stack).top = 0, (stack).max = 0)
#endif

#ifndef STACK_PUSH
#define STACK_PUSH(stack, value) \
    (((stack).elements)[(stack).top++] = (value))
#endif

#ifndef STACK_POP
#define STACK_POP(stack, value) \
    ((value) = ((stack).elements)[--(stack).top])
#endif


#ifndef STACK_TOP
#define STACK_TOP(stack, value) \
   ( (temp)=  (stack).top  ,((value) = ((stack).elements)[--temp])  )
#endif

//EvalExpression.c

#include

#define STACK_ELEMENT_TYPE  char
#define STACK_TYPE          CharStack
#include "stack_template.h"
#undef STACK_ELEMENT_TYPE
#undef STACK_TYPE

#define STACK_ELEMENT_TYPE  int
#define STACK_TYPE          IntStack
#include "stack_template.h"
#undef STACK_ELEMENT_TYPE
#undef STACK_TYPE

typedef enum{
	lparen,rparen,plus,minus,times,divide,eos,operand
} precedence;


//    
int  precede(char stacktop,char op);
void Postfix(const char *expr , char output[] );
int Eval(char expr[]);
precedence GetToken(char expr[], char * symbol ,int *n);

//          
int Eval(char postfix[])
{

	char symbol;
	int op1,op2;
	int n=0;
	precedence token=GetToken(postfix,&symbol ,&n);
	IntStack intstack;
	STACK_INIT(intstack, 20);
	while(token !=eos)
	{
		if(token==operand)
			STACK_PUSH(intstack, symbol-'0');
		else
		{
			STACK_POP(intstack, op2);
			STACK_POP(intstack, op1);
			switch(token)
			{
				case plus:  STACK_PUSH(intstack, op1+op2 );break;
				case minus: STACK_PUSH(intstack, op1-op2 );break;
				case times: STACK_PUSH(intstack, op1*op2 );break;
				case divide:STACK_PUSH(intstack, op1/op2);break;
			}
		}
		token=GetToken(postfix,&symbol,&n);
	}
	int result=0;
	STACK_POP(intstack, result);
	STACK_DESTROY(intstack);
	return result;
}

precedence GetToken(char expr[], char * symbol ,int *n)
{
	*symbol=expr[ (*n)++ ];
	switch( *symbol)
	{
		case '(': return lparen;
		case ')': return rparen;
		case '+': return plus;
		case '-': return minus;
		case '*': return times;
		case '/': return divide;
				  //case '%': return mod;
		case '\0': return eos;
		default : return operand;
	}
}


//             
//         10         ，               ，           ,
//           ，               .
//                       ，           ，  C++      .

/*
 *                       。                ，         255。
 */
void Postfix(const char *expr , char output[] )
{
	if(!expr)
		printf("the expression is null
");
	char symbol;
	int i=0;
	CharStack charstack;
	STACK_INIT(charstack, 10);
	STACK_PUSH(charstack, '#');//                    ，       ，         。
	for( ;*expr!='\0';expr++)
	{
		if(*expr>='0'&& *expr <='9' )
			output[i++]=*expr;

		else if(*expr==')')
		{
			while(1)
			{
				STACK_POP(charstack, symbol);
				if( symbol!='(')
					output[i++]=symbol;
				else
					break;
			}
		}
		else //        lparen
		{
			char stacktop;
			STACK_TOP(charstack, stacktop);
			if( precede(stacktop, *expr)<0 )                         
				STACK_PUSH(charstack, *expr);
			else
				output[i++]=*expr;
		}

	}
	while(1) //         ，         #     。           
	{
		STACK_POP(charstack, symbol);
		if( symbol!='#')
			output[i++]=symbol;
		else
			break;
	}
	output[i]='\0';
	STACK_DESTROY(charstack);
}


//  2        
int  precede(char stacktop,char op)
{
	int i,j;
	int prior[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}};

	switch(stacktop)
	{
		case '+':i=0;break;
		case '-':i=1;break;
		case '*':i=2;break;
		case '/':i=3;break;
		case '(':i=4;break;
		case ')':i=5;break;
		case '#':i=6;break; 
	}
	switch(op){
		case '+':j=0;break;
		case '-':j=1;break;
		case '*':j=2;break;
		case '/':j=3;break;
		case '(':j=4;break;
		case ')':j=5;break;
		case '#':j=6;break; 
	}   

	return prior[i][j];
}

int main()
{
	char expr[20]="(1*(2+3)*4)+1";
	char output[20];
	//scanf("%s",expr);
        printf("      ：%s
",expr);
	Postfix(expr,output);
	printf("      ：%s
",output);
	int result=Eval(output);
	printf("     ：%d
",result);
	return;
}