[C++知识库]基于栈的后缀表达式（c语言）

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

typedef struct stack{
    char *data;
    int top;
    int stacksize;
}sqstack, *Stack;

int initStack(Stack s,int max){
    s->data = (char *)malloc(sizeof(char)*max);
    if(s->data==NULL){
        printf("initError");
        exit(0);
    }
    s->top = -1;
    s->stacksize=max;
    return 1;
}

int isStackEmpty(sqstack s){
    if(s.top=-1){
        return 1;
    }
    else{
        return 0;
    }
}
int Push(Stack s,char e){
    if(s->stacksize == s->top+1)return 0;
    s->top++;
	s->data[s->top]=e;
    return 1;
}
int Pop(Stack s,char *e){
    if(s->top==-1)return 0;
    else{
        *e = s->data[s->top];
        s->top--;
        return 1;
    }
}

int getStackTop(sqstack s,char *e){
    if(s.top==-1)return 0;
    else{
        *e = s.data[s.top];
        return 1;
    }
}

int prior(char e){
    switch (e)
    {
    case '*':return 4;break;
	case '/':return 4;break;
    case '+':return 3;break;
	case '-':return 3;break;
    case '(':return 2;break;
    case '#':return 1;break;
    default:
        return 0;
        break;
    }
}

void Transformation(char a[], char suff[]){
    int i=0,k=0,n;
    char ch;
    sqstack s;
    initStack(&s,20);
    Push(&s,'#');

    n = strlen(a);
    a[n] = '#';
    a[n+1] = '\0';
    while(a[i] != 0){
        if(a[i]>= '0' && a[i] <= '9')suff[k++] = a[i];
        else{
            switch(a[i]){
                case '(':Push(&s,a[i]);break;
                case ')':
                    Pop(&s,&ch);
                    while(ch != '('){
                        suff[k++] = ch;
                        Pop(&s,&ch);
                    }
                	break;
                default:
                    getStackTop(s,&ch);
                    while(prior(ch)>prior(a[i])){
                        suff[k++] = ch;
                        Pop(&s,&ch);
                        getStackTop(s,&ch);
                    }
                    if(a[i] !='#')Push(&s,a[i]);
                    break;
            }
        }
       i++;
       
    }
    suff[k]='\0';

	return;
}

void suffix_value(char a[]){
    sqstack s;
    int i=0,n;
    char x1,x2;
    initStack(&s,20);
    n=strlen(a);
    a[n]='#';
    a[n+1]='\0';
    puts(a);
    while(a[i] !='#'){
        switch(a[i]){
            case '+':Pop(&s,&x2);Pop(&s,&x1);Push(&s,(char)(x1-48+x2));break;
            case '-':Pop(&s,&x2);Pop(&s,&x1);Push(&s,(char)(x1-x2+48));break;
            case '*':Pop(&s,&x2);Pop(&s,&x1);Push(&s,(char)((x1-48)*(x2-48)+48));break;
            case '/':Pop(&s,&x2);Pop(&s,&x1);
                if(x2!=0){
					Push(&s,(char)((x1-48)/(x2-48)+48));
					}
                else{
                    printf("分母为0!\n");return;
                    break;
                }
                break;
            default:
                Push(&s,a[i]);
                break;
        }
        i++;
    }
    Pop(&s,&x1);
    printf("结果为=%d\n",x1-48);
}

void menu(){
	printf("******菜单******\n");
	printf("1.求后缀表达式\n");
	printf("2.求值\n");
	printf("输入0退出\n");
	printf("****************\n");
}
int main(){
    char a[30];
    char suff[30];
    int choice;
    menu();
	printf("输入选择：\n");
    for(scanf("%d",&choice);choice!=0;scanf("%d",&choice)){
    	switch(choice){
    		case 1:
    			scanf("%s",&a);
    			Transformation(a,suff);
    			printf("后缀表达式:%s\n",suff);
    			break;
    		case 2:
    			suffix_value(suff);
    			break;
    		default:
    			break;
		}
		menu();
		printf("输入选择：\n");
	}
}