堆栈 表达式的转换（后缀表达式）

Question

#include<stdio.h>
#include<stdlib.h>
typedef char Element;//
struct snode{
    Element data;
    struct snode* next;
};
typedef struct snode* Stack;
Stack createstack();//建立空栈 
void push(Element item,Stack S);
int isempty(Stack S);
void pop(Stack S);
int compare(Element item,Element ch);
int sign=0;
int main(){
    Stack L;
    L=createstack();
    Element ch;
    int flag=1;
    int fuhao=0;
    while(1){
        scanf("%c",&ch);
        if(ch==')')sign=1;
        if(ch=='\n')break;//
        else if(ch>='0'&&ch<='9'){
            if(flag==1)printf("%c",ch);
            else printf(" %c",ch);
            flag=0;
            fuhao=1;
        }
        else if(fuhao==0){
        printf("%c",ch);    
    }
        else push(ch,L);
    }
    Stack p=L;
    while(p->next !=NULL){////剩下的符号 
    printf(" %c",p->next->data );
    p=p->next ;
}
}
Stack createstack(){
    Stack S; 
    S=(Stack)malloc(sizeof(struct snode));
    S->next =NULL;
    return S;
} 
int isempty(Stack S){
    return (S->next ==NULL); 
}
void push(Element item,Stack S){
    while(sign==1){//遇到右括号打印括号里面的内容 
        pop(S);
        if(S->next->data =='(' )break;
    }
    if(sign==1){
    pop(S);
    sign=0;    
    return ;
}
    while(S->next !=NULL&&compare(S->next->data ,item)){//熔断 
        pop(S);
    }
    if(item!=')'){
    Stack tmpcell;
    tmpcell=(Stack)malloc(sizeof(struct snode));
    tmpcell->data=item;
    tmpcell->next=S->next;
    S->next =tmpcell;
}
}
void pop(Stack S){
    if(isempty(S))return;
    struct snode* first;
    Element ch;
    first=S->next ;
    S->next =first->next ;
    ch=first->data ;
    free(first);
    if(ch!='('&&ch!=')')printf(" %c",ch);//左右括号不打印 
}
int compare(Element top,Element ch){
    if(ch=='('||top=='(')return 0;//算法 
    if(ch==')')return 1;
    switch(ch){//1顶弹出 
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            switch(top){
                case '*':
                case '/':
                    return 1;
                case '+':
                case '-':
                    return 0;
            }
    }
}

感觉已经写的差不多了，输出结果似样例，为什么还是答案错误？还有嵌套括号处理的不对么？

Answer 1

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

//用一个结构体来绑定一个运算项和其优先级
typedef struct Number number;
struct Number {
    char c;//运算数或运算符
    int priority;//优先级
};
/*
 各项的类型 优先级
 数字        0
 + -        1
 * /        2
 ( )        3
 */

 //链栈的节点
typedef struct StackNode* stack;
struct StackNode {
    number* data;
    stack next;
};

//栈的生成方法
stack makeStack() {
    stack s = (stack)malloc(sizeof(struct StackNode));
    s->data = (number*)malloc(sizeof(struct Number));
    s->next = NULL;
    return s;
}

//判断栈是否空
bool isEmpty(stack s) {
    return s->next == NULL;
}
//入栈
bool Push(stack s, number* x) {
    stack newnode = (stack)malloc(sizeof(struct StackNode));
    newnode->data = x;
    newnode->next = s->next;
    s->next = newnode;
    return true;
}
//出栈
char Pop(stack s) {
    if (isEmpty(s)) {
        return -1;
    }
    stack temp = s->next;
    char back = temp->data->c;
    s->next = temp->next;
    free(temp);
    return back;

}

//中缀转后缀方法
void FromMiddleToPost() {

    char c = '\0';//用来接收读取到的字符
    int count = 0;//记录数组内的元素个数
    number num[100];//结构体数组 用来记录读取到的中缀表达式并给各项附上优先级
    while (1) {
        scanf("%c", &c);//根据读取到的各项做具体处理
        if (c == ' ') {//空格的情况 直接跳过
            continue;
        }
        else if (c == '+' || c == '-') {
            num[count].c = c;
            num[count++].priority = 1;
        }
        else if (c == '*' || c == '/') {
            num[count].c = c;
            num[count++].priority = 2;
        }
        else if (c == '(') {
            num[count].c = c;
            num[count++].priority = 3;//左括号
        }
        else if (c == ')') {
            num[count].c = c;
            num[count++].priority = 4;//右括号
        }
        else {//数字的情况
            num[count].c = c;
            num[count++].priority = 0;
        }
        if (c == '\n') {//读取到回车 结束输入
            break;
        }
    }
    num[count].c = '\0';//数组的最后放入\0

    stack s = makeStack();//创建栈

    //开始从num数组中读取各种并转化成后缀表达式
    for (int i = 0; i < count; i++) {
        if (num[i].c == '\n') {//扔掉回车符
            continue;
        }
        if (num[i].priority == 0) {//读取到数字 直接输出
            printf("%c", num[i].c);
        }
        else {
            if (isEmpty(s)) {//空表的情况下 无论什么运算符 直接插入
                Push(s, &num[i]);
            }
            else {
                if (num[i].priority == 3) {//处理左右括号的情况
                    Push(s, &num[i]);
                }
                else if (num[i].priority == 4) {//右括号
                    char temp = Pop(s);
                    printf("%c", temp);
                    while (s->next != NULL && temp != '(') {
                        temp = Pop(s);
                        if (temp != '(') {
                            printf("%c", temp);
                        }
                    }
                }
                else if (s->next->data->priority < num[i].priority) {//后插入的优先级 比 栈顶的优先级高
                    Push(s, &num[i]);
                }
                else {//后插入的优先级 小于等于 栈顶元素
                    while (s->next != NULL && s->next->data->priority >= num[i].priority) {//弹出栈 直到栈顶元素的优先级 小于 当前元素的优先级

                        if (s->next->data->priority == 3) break;//当栈顶字符是'('时 直接入栈即可 
                        char temp = Pop(s);
                        printf("%c", temp);
                    }
                    Push(s, &num[i]);
                }
            }
        }
    }
    while (s->next != NULL) {//弹出栈内剩余的运算符
        char temp = Pop(s);
        printf("%c", temp);
    }
    printf("\n");
}


int main() 
{ 
    FromMiddleToPost();
    return 0;
}