Description

"I have a dream that one day I can become a calculator."

~by anonymous Asian

But you are a programmer(you have no life). You can design a program to calculate for you(and become shame of Asian).

The input will contain multiple expression and end by EOF.

Each expression will only contain +, -, *, /, % and numbers(No parentheses).

You need to calculate the answer of the expression.

There may be several blanks or no blanks between operator and number.

You can use the code below and just finish the "Todo" part.

You can write your own code too.

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
​
#define MAX_LENGTH 1000
​
// Token / AST kinds
enum {
    // Non-operators
    Value,
    // Operators
    /// Precedence 1
    Mul, Div, Rem,
    /// Precedence 2
    Add, Sub,
};
typedef struct _TOKEN {
    int kind;
    int param; // Value
    struct _TOKEN *prev, *next;
} Token;
typedef struct _AST {
    int type;
    int val; // Value
    struct _AST *lhs, *rhs;
} AST;
​
// Utility Interface
​
// Used to create a new Token.
Token *new_token(int kind, int param);
// Used to create a new AST node.
AST *new_AST(Token *mid);
// Convert Token linked list into array form.
int list_to_arr(Token **head);
// Use to check if the kind can be determined as a value section.
int isValueSection(int kind);
// Function called when an unexpected expression occurs.
void err();
​
// Used to find a appropriate operator that split the expression half.
int find_Tmid(Token *arr, int l, int r);
//get the Precedence of operator or value
int getOpLevel(int kind);
// calculate the answer 
void getanswer(AST *ast);
​
// Main Function
​
char input[MAX_LENGTH];
int regis[1000], now_reg = -1;
​
// Convert the inputted string into multiple tokens.
Token *lexer(char *in);
// Use tokens to build the binary expression tree.
AST *parser(Token *arr, int l, int r);
// calculate the answer
void calculate(AST *ast);
​
int main() {
    while(fgets(input, MAX_LENGTH, stdin) != NULL) {
        // build token list by lexer
        Token *content = lexer(input);
        // convert token list into array
        int length = list_to_arr(&content);
        
        // build abstract syntax tree by parser
        AST *ast_root = parser(content, 0, length-1);
        // calculate the answer
        calculate(ast_root);
        
        /*Todo*/
        // print the answer here.
        
        /*Todo*/
        // do some reset??
    }
    return 0;
}
AST *parser(Token *arr, int l, int r) {
    if(l > r) return NULL;
    // covered in parentheses
    int mid = find_Tmid(arr, l, r);
    AST *newN = new_AST(arr + mid);
    
    if(l == r || newN->type == Value)
        return newN;
​
    /*Todo*/
    //finish the parser
    return newN;
}
AST* new_AST(Token *mid) {
    AST *newN = (AST*)malloc(sizeof(AST));
    newN->lhs = newN->rhs = NULL;
    newN->type = mid->kind;
    newN->val = mid->param;
    return newN;
}
int find_Tmid(Token *arr, int l, int r) {
    /*Todo*/
    //find the node to be contructed
}
int getOpLevel(int kind) {
    /*Todo*/
    // you may use this finction in find_Tmid
}
void calculate(AST *ast) {
    /*Todo*/
    // traverse the tree by postorder
}
​
void getanswer(AST *ast){
    /*Todo*/
    // calculate the answer here.
    // you can calculate the answer by simulating the registers
}
​
Token *lexer(char *in) {
    Token *head = NULL;
    Token **now = &head, *prev = NULL;
    for(int i = 0; in[i]; i++) {
        if(in[i] == ' ' || in[i] == '\n')
            continue;
​
        else if(isdigit(in[i])) {
            int val = 0, oi = i;
            for(; isdigit(in[i]); i++)
                val = val * 10 + (in[i] - '0');
            i--;
            // Detect illegal number inputs such as "01"
            if(oi != i && in[oi] == '0')
                err();
            (*now) = new_token(Value, val);
        }
​
        else {
            switch(in[i]) {
                case '+': // '+'
                    (*now) = new_token(Add, 0);
                    break;
                case '-':
                    (*now) = new_token(Sub, 0);
                    break;
                case '*':
                    (*now) = new_token(Mul, 0);
                    break;
                case '/':
                    (*now) = new_token(Div, 0);
                    break;
                case '%':
                    (*now) = new_token(Rem, 0);
                    break;
                default:
                    err();
            }
        }
        (*now)->prev = prev;
        if(prev != NULL) prev->next = (*now);
        prev = (*now);
        now = &((*now)->next);
    }
    return head;
}
Token *new_token(int kind, int param) {
    Token *res = (Token*)malloc(sizeof(Token));
    res->kind = kind;
    res->param = param;
    res->prev = res->next = NULL;
    return res;
}
int list_to_arr(Token **head) {
    int res = 0;
    Token *now = (*head), *t_head = NULL, *del;
    while(now!=NULL) {
        res++;
        now = now->next;
    }
    now = (*head);
    t_head = (Token*)malloc(sizeof(Token)*res);
    for(int i = 0; i < res; i++) {
        t_head[i] = (*now);
        del = now;
        now = now->next;
        free(del);
    }
    (*head) = t_head;
    return res;
}
int isValueSection(int kind) {
    if(kind == Value) return 1;
    return 0;
}
void err(){
    exit(0);
}
​

 

 

 

 

Input

The input will contain multiple expression and end by EOF.

Each expression will only contain +, -, *, /, % and numbers(No parentheses).

Each expression will not exceed 10000 characters.

We guarantee that every expression is legal.

Output

For each expression print the answer you calculate.

remember to print \n at every end of answer.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss