天天看點

中綴表達式轉化成字尾表達式并計算結果

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 1024

void print(char *postexp){
    while(*postexp != '\0'){
        printf("%c",*postexp);
        postexp++;
    }
    printf("\n");
}
void change(char* exp,char postexp[]){
    //定義棧 
    char st[MaxSize];
    int top = -1;
    int i = 0,k = 0;
	//規則:棧頂元素比目前處理元素優先級高時出棧,之後目前元素進棧。
    while(*exp != '\0'){
        switch(*exp){
            case '('://左括号直接進棧
                st[++top] = *exp;
                exp++;
				break;
            case ')':
				//右括号時出棧元素直到左括号,左括号也出棧
                while(top != -1 || st[top] != '('){
                    postexp[k++] = st[top--];
                }
                exp++;
				break;
            case '+':
            case '-':
				//棧不空且棧頂不為左括号時出棧
				while(top != -1 && st[top] != '('){
					postexp[k++] = st[top--];
					
				}
				//進棧
                st[++top] = *exp;
                exp++;
				break;
            case '*':
            case '/':
				//棧不空且棧頂為‘*’或‘/’時出棧
                while(top != -1 && (st[top] == '*' || st[top] == '/')){
                    postexp[k++] = st[top--];
                }
				st[++top] = *exp;
                exp++;
				break;
            default:
				//擷取整數并進棧,整數以‘#’結尾
                while(*exp >= '0' && *exp <= '9'){
                    postexp[k++] = *exp;
                    exp++;
                }
                postexp[k++] = '#';
        }
    }
	//棧不為空時進棧
    while(top != -1){
        postexp[k++] = st[top--];
    }
	postexp[k] = '\0';
}

int value(char* postexp){
    int st[MaxSize];
    int top = -1;
    
	int sum = 0;
    int firstA = 0,secondA = 0;
    
    while(*postexp != '\0'){
        switch(*postexp){
            case '+':
                firstA = st[top--];
                secondA = st[top--];
                secondA += firstA;
                st[++top] = secondA;
                break;
            case '-':
                firstA = st[top--];
                secondA = st[top--];
                secondA -= firstA;
                st[++top] = secondA;
                break;
            case '*':
                firstA = st[top--]; 
                secondA = st[top--];
                secondA *= firstA;
                st[++top] = secondA;
                break;
            case '/':
                firstA = st[top--];
                secondA = st[top--];
                if(firstA == 0){
                    printf("除零錯誤!!!");
                    exit(0);
                }
                secondA /= firstA;
                st[++top] = secondA;
                break;
            default:
                while(*postexp >= '0' && *postexp <= '9'){
                    sum += *postexp - '0';
                    postexp++;
                }
                st[++top] = sum;
        }
        postexp++;
    }
    return st[top];
}

int main(){
    char exp[18] = "2+3*(432-2)/10-86";
    char postexp[MaxSize];
    change(exp,postexp);
	printf("中綴表達式:%s",exp);
	printf("字尾表達式:%s",postexp);
    print(postexp);
	printf("表達式結果值:%d",value(postexp));
    
    return 1;
}
           

繼續閱讀