Problem Description

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

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

转换为后缀表示为：

ABC*D十E*--FG十／

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

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

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

输出
N个后缀表达式。

测试输入

1
(A-(B*C+D)*E)/(F+G)#

测试输出

ABC*D+E*-FG+/

AcCode

//
//  main.cpp
//  从中缀向后缀转换表达式
//
//  Created by jetviper on 2017/3/26.
//  Copyright © 2017年 jetviper. All rights reserved.
//


#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include<string.h>
#define true 1
#define false 0
typedef struct Node
{
    char data;
    struct Node *pNext;
}NODE, *PNODE;
typedef struct Stack
{
    PNODE pTop;
    PNODE pBottom;
}STACK, *PSTACK;
//栈的初始化
void init(PSTACK pS)
{
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    pS->pBottom = pS->pTop;
    pS->pTop->pNext = NULL;
    return;
}
//插入元素到栈顶
void push(PSTACK pS, char val)
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    pNew->data = val;
    pNew->pNext = pS->pTop;
    pS->pTop = pNew;
    return;
}
//判断栈是否为空
int empty(PSTACK pS)
{
    if (pS->pTop == pS->pBottom)
    {
        return true;
    }
    else
        return false;
}

void deltop(PSTACK pS) {
    pS->pTop = pS->pTop->pNext;
    return;
}

int main(void)
{
    int n;
    scanf("%d", &n);
    while (n--) {
        
        STACK czf;
        PSTACK p1=&czf;
        init(p1);
        push(p1, '#');
        char ch,op,str[100];
        
        int icp, isp,i=0;
        scanf("%s", &str);
        while(1) {
            ch = str[i];
            if (ch > 64 && ch < 91 || ch>96 && ch < 123) {
                printf("%c", ch);
                i++;
                continue;
            }
            else {
                op = p1->pTop->data;
                switch (op) {
                    case '#': {isp = 0; break; }
                    case '(': {isp = 1; break; }
                    case '^': {isp = 6; break; }
                    case '*': {isp = 5; break; }
                    case '/': {isp = 5; break; }
                    case ')': {isp = 8; break; }
                    case '+': {isp = 3; break; }
                    case '-': {isp = 3; break; }
                }
                switch (ch) {
                    case '#': {icp = 0; break; }
                    case '(':{icp = 8; break; }
                    case '^':{icp = 7; break; }
                    case '*':{icp = 4; break; }
                    case '/':{icp = 4; break; }
                    case ')':{icp = 1; break; }
                    case '+':{icp = 2; break; }
                    case '-':{icp = 2; break; }
                }
                
                if (icp > isp) {
                    push(p1, ch);
                    i++;
                    continue;
                }
                if (icp < isp) {
                    deltop(p1);
                    printf("%c", op);
                    continue;
                }
                if (icp == isp) {
                    if (op == '(') {
                        deltop(p1);
                        i++;
                        continue;
                    }
                    else {
                        deltop(p1);
                        if(op!='#')continue;
                        else break;
                    }
                    
                }
                
            }
            
        }
        
        printf("\n");
        
    }
    
    return 0;
}