6.从中缀向后缀转换表达式

浅浅的花香味﹌ 2022-04-06 04:58 144阅读 0赞

## 6.从中缀向后缀转换表达式 ##

**问题描述**

中缀表达式就是我们通常所书写的数学表达式，后缀表达式也称为逆波兰表达式，在编译程序对我们书写的程序中的表达式进行语法检查时，往往就可以通过逆波兰表达式进行。我们所要设计并实现的程序就是将中缀表示的算术表达式转换成后缀表示，例如，将中缀表达式

(A 一 (B\*C 十 D)\*E) ／ (F 十 G )

转换为后缀表示为：

ABC\*D十E\*--FG十／

**注意：**为了简化编程实现，假定变量名均为单个字母，运算符只有＋，－，＊，／ 和＾（指数运算），可以处理圆括号（），并假定输入的算术表达式正确。

**要求：**使用栈数据结构实现 ，输入的中缀表达式以＃号结束

## **输入** ##

整数N。表示下面有N个中缀表达式  
N个由单个字母和运算符构成的表达式

## **输出** ##

N个后缀表达式。

#include "stdio.h"
    #include "ctype.h"
    #include "stdlib.h"
    typedef struct Node
    {
        char symbol;
        struct Node * next;
    }NODE;
    NODE *head, *p;
    
    void InitStack(){
        head = (NODE*)malloc(sizeof(NODE));
        head->symbol = NULL;
        head->next = NULL;
    }
    
    void Push(char ch){
        p = (NODE*)malloc(sizeof(NODE));
        p->symbol = ch;
        p->next = head->next;
        head->next = p;
    }
    
    void Pop(){
        p = head->next;
        head->next = p->next;
        free(p);
    }
    int main(){
        int N;
        char ch;
        scanf("%d\n",&N);
        while(N--){
            InitStack();
            while((ch = getchar()) && ch != '#'){
                if(isalnum(ch)){
                    putchar(ch);
                }
                else if(ch == '('){
                    Push(ch);
                }
                else if(ch == ')'){
                    while(head->next->symbol != '('){
                        putchar(head->next->symbol);
                        Pop();
                    }
                    Pop();
                }
                else{
                    if(head->next == NULL){
                        Push(ch);
                    }
                    else{
                        int x, y;//x=ch,y=top of the stack
                        while(1){
                            if(head->next == NULL){
                                Push(ch);
                                break;
                            }
                            char ch1 = head->next->symbol;
                            switch(ch){
                                
                             
                                case '^':{x = 7; break; }
                                case '*':{x = 4; break; }
                                case '/':{x = 4; break; }
                            
                                case '+':{x = 2; break; }
                                case '-':{x = 2; break; }
                            }
                            switch(ch1){
                                
                               
                                case '^': {y = 6; break; }
                                case '*': {y = 5; break; }
                                case '/': {y = 5; break; }
                                case '(': {y = 1; break; }
                                case '+': {y = 3; break; }
                                case '-': {y = 3; break; }
                            }
                            if(y > x || y == x){
                                putchar(ch1);
                                Pop();
                                continue;
                            }
                            else{
                                Push(ch);
                                break;
                            }
                        }
                    }
                }
            }
            //当全部遍历结束的时候进行的操作
            while(head->next != NULL){
                putchar(head->next->symbol);
                Pop();
            }
            putchar('\n');
            ch = getchar();
        }
    }