Description

Kuo-chan wants to build a syntax tree for infix algebraic expressions with number, addition, subtraction, and parentheses.

To parse the infix expressions, he can use the grammar below.

EXPR = FACTOR | EXPR OP FACTOR

FACTOR = ID | (EXPR)

EXPR is the expression. ID is the number. OP is either + (addition) or - (subtraction).

Please help Kuo-chan to build the syntax tree.

You can use the following default code:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h> //for isdigit() 

typedef struct _Node {
    int value;
    char OP;
    struct _Node *left;
    struct _Node *right;
} Node;

char expr[120];
int pos;
Node *head;

Node* Factor();
Node* Expr();
void PrefixPrint(Node* node);

Node* CreateNode(int value , char ch) {
    Node *newNode;
    newNode = (Node*) malloc(sizeof(Node));
    
    if(ch == 'N') {
        newNode->value = value;
        newNode->OP = 'N';
    }
    else {
        newNode->value = -1;
        newNode->OP = ch;
    }
    return newNode;
}

int main() {
    while((scanf("%s" , expr)) != EOF) {
        pos = strlen(expr) - 1;
        head = Expr();
        PrefixPrint(head);
        printf("\n");
        head = NULL; 
    }
    
    return 0;
}

Input

There're multiple testcases. 

Every number is positive and smaller than 10⁹.

All parentheses are matched. 

The length of every input is at most 100.

 

Different testcases have different constraints.

1. All number is smaller than 10. No parentheses.
2. All number is smaller than 10. No nested parentheses such as (1+(2)), but (1)+(2) is permitted.
3. All number is smaller than 10. 
4. No parentheses.
5. No nested parentheses.
6. No extra constraints.

Output

The output contains N prefix expressions without parentheses, which are preorders of syntax trees.

Please ouput a whitespace after every number, addition, and subtraction. Read the sample output for more detail.

Remember to add new line in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 

Input

The input contains Q lines.

Initially, A is empty.

Each of the Q lines describes the operations Yang-chan performs. Each line is one of four types:

1. PUSH x  (1 ≤ x ≤ 10⁹ )
2. POP
3. PROGRAMMING TANOSHI k ( 1 ≤ k ≤ 9 )
4. IP2 SUGOI

 

Different testcases have different constraints.

1. Q ≤ 2*10³, operations: { PUSH, POP }
2. Q ≤ 2*10³, operations: { PUSH, POP, PROGRAMMING TANOSHI }
3. Q ≤ 2*10³, operations: { PUSH, POP, PROGRAMMING TANOSHI, IP2 SUGOI }
4. Q ≤ 3*10⁵, operations: { PUSH, POP }
5. Q ≤ 3*10⁵, operations: { PUSH, POP, PROGRAMMING TANOSHI }
6. Q ≤ 3*10⁵, operations: { PUSH, POP, IP2 SUGOI }
7. Q ≤ 3*10⁵, operations: { PUSH, POP, PROGRAMMING TANOSHI, IP2 SUGOI }
8. Q ≤ 3*10⁵, operations: { PUSH, POP, PROGRAMMING TANOSHI, IP2 SUGOI }

Note: You can include <math.h> to use sqrt(x). sqrt(x) returns the square root of x. Just be careful with roundoff error.

          You can also use ceil(x), floor(x) included in <math.h>.

Hint: To speed up the code, you can think about how many operations will an element be performed at most.

Update: 1.  Make use of  the variable all_operation to store {PROGRAMMING TANOSHI, IP2 SUGOI} operations.

              2. You can think that if a number becomes 1  you won't need to do any operation on it anymore.

Output

You should print one line containing the elements of A after the operations. For 1 ≤ i ≤ |A|, the i-th number should be A[ i ].

Sample Input  Download

Sample Output  Download

Partial Judge Code

13141.c

Partial Judge Header

13141.h

Tags

Discuss