[データ構造]接尾辞から接尾辞への変換式の解題レポート

4097 ワード

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 
#include 
#include 
#include
#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("
"); } return 0; }