Skip to content

11033: 【原1033】表达式求值

题目

题目描述

author: zyz 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1033

Description

二哥想自己做一个计算器,但是他需要一个程序来计算输入表达式的结果。你能帮助他吗?

Input Format

输入仅一行,给出一个算数表达式。表达式中包含:小括号,加减乘除,指数运算符,负号,整数,空格。其中负号的优先级最高(-),其次是指数运算(^),然后是乘除(*/),最后是加减(+-)。

这里规定除法为整除运算,如 5 / 2 = 2, 8 / -3 = -2 等等,与C++中的整除一致。另外注意指数运算为右结合,即 2^3^2 = 2^9 = 512 而非 2^3^2 = 8^2 = 64 。

输入的字符串长度不超过100。

Output Format

如果输入的表达式出现括号不匹配或者除零错误,输出一行“Error”(不含引号),否则输出运算结果。输入保证不包含任何其它类型的错误。

输入的数,输出的答案,以及中间结果均保证是不超过 long long 范围的整数。

Sample Input

5 + (1 + 3) * 6 ^ 1

Sample Output

29

Sample Input

(6 + 2)) * 3

Sample Output

Error

说明

30%的测试数据含有负号;

30%的测试数据含有指数运算。

FineArtz's solution

/* 表达式求值 */
#include <iostream>
#include <cmath>
#include <stdexcept>
using namespace std;

enum OptType {ADD, SUB, MUL, DIV, BRACKET, EXP, POS, NEG, NONE};
enum TokenType {DIGIT, OPT, VOID};

class Opt{
public:
    Opt() : opt(' '), type(NONE), predency(-2) {}
    Opt(char ch) : opt(ch){
        switch(ch){
        case '+':
            type = ADD;
            predency = 1;
            break;
        case '-':
            type = SUB;
            predency = 1;
            break;
        case '*':
            type = MUL;
            predency = 2;
            break;
        case '/':
            type = DIV;
            predency = 2;
            break;
        case '(':
            type = BRACKET;
            predency = 0;
            break;
        case '^':
            type = EXP;
            predency = 3;
            break;
        case '&':
            type = POS;
            predency = 4;
            break;
        case '|':
            type = NEG;
            predency = 4;
            break;
        case ')':
            type = BRACKET;
            predency = 10;
            break;
        default:
            throw runtime_error("fuck it");
            break;
        }
    }
    OptType getType() { return type; }
    int getPred() { return predency; }
    char getOpt() { return opt; }
private:
    char opt;
    OptType type;
    int predency;
};

long long qpow(long long x, long long n){
    long long ans = 1, tmp =x;
    while (n > 0){
        if (n & 1) ans *= tmp;
        n >>= 1;
        tmp *= tmp;
    }
    return ans;
}

long long operate(long long x, long long y, Opt opt){
    switch(opt.getOpt()){
    case '+':
        return x + y;
    case '-':
        return x - y;
    case '*':
        return x * y;
    case '/':
        if (y == 0) throw runtime_error("fuck it");
        return x / y;
    case '^':
        return qpow(x, y);
    default:
        throw runtime_error("fuck it");
    }
}

char suf[200];
int sufSize = 0;

void infToSuf(){
    char ch;
    long long curNum = 0x7fffffff;
    TokenType lastTokenType = VOID;
    Opt optStack[200];
    int optSize = 0;

    while (cin >> ch){
        if (isdigit(ch)){
            if (curNum == 0x7fffffff) curNum = 0;
            curNum = curNum * 10 + ch - '0';
            lastTokenType = DIGIT;
        }
        else{
            if (lastTokenType == DIGIT && curNum != 0x7fffffff){
                if (curNum != 0){
                    int dec = ceil(log10(curNum));
                    if (abs(dec - log10(curNum)) < 1e-6) ++dec;
                    while (dec > 0){
                        suf[sufSize++] = curNum / qpow(10, dec - 1) + '0';
                        curNum %= qpow(10, dec - 1);
                        --dec;
                    }
                }
                else{
                    suf[sufSize++] = '0';
                }
                curNum = 0x7fffffff;
                suf[sufSize++] = '#';
            }
            Opt curOpt(ch);
            switch(curOpt.getOpt()){
            case ')':
                while (optSize > 0 && optStack[optSize - 1].getOpt() != '('){
                    suf[sufSize++] = optStack[--optSize].getOpt();
                }
                if (optSize == 0){
                    throw runtime_error("fuck it");
                }
                if (optStack[--optSize].getOpt() != '('){
                    throw runtime_error("fuck it");
                }
                lastTokenType = DIGIT;
                break;
            case '(':
                optStack[optSize++] = curOpt;
                lastTokenType = OPT;
                break;
            case '-': case '+':
                if (lastTokenType == VOID || lastTokenType == OPT){
                    lastTokenType = OPT;
                    if (curOpt.getOpt() == '-'){
                        Opt tmpOpt('|');
                        optStack[optSize++] = tmpOpt;
                    }
                    else{
                        Opt tmpOpt('&');
                        optStack[optSize++] = tmpOpt;
                    }
                    break;
                }
            case '*': case '/':
                if (optSize == 0 || curOpt.getPred() > optStack[optSize - 1].getPred()){
                    optStack[optSize++] = curOpt;
                }
                else{
                    while (optSize > 0 && curOpt.getPred() <= optStack[optSize - 1].getPred()){
                        suf[sufSize++] = optStack[--optSize].getOpt();
                    }
                    optStack[optSize++] = curOpt;
                }
                lastTokenType = OPT;
                break;
            case '^':
                if (optSize == 0 || curOpt.getPred() >= optStack[optSize - 1].getPred()){
                    optStack[optSize++] = curOpt;
                }
                else{
                    while (optSize > 0 && curOpt.getPred() < optStack[optSize - 1].getPred()){
                        suf[sufSize++] = optStack[--optSize].getOpt();
                    }
                    optStack[optSize++] = curOpt;
                }
                lastTokenType = OPT;
                break;
            }
        }
    }
    if (lastTokenType == DIGIT && curNum != 0x7fffffff){
        if (curNum != 0){
            int dec = ceil(log10(curNum));
            if (abs(dec - log10(curNum)) < 1e-6) ++dec;
            while (dec > 0){
                suf[sufSize++] = curNum / qpow(10, dec - 1) + '0';
                curNum %= qpow(10, dec - 1);
                --dec;
            }
        }
        else{
            suf[sufSize++] = '0';
        }
        curNum = 0x7fffffff;
        suf[sufSize++] = '#';
    }
    while (optSize > 0){
        if (optStack[--optSize].getOpt() == '('){
            throw runtime_error("fuck it");
        }
        suf[sufSize++] = optStack[optSize].getOpt();
    }
}

long long calcSuf(){
    long long numStack[200];
    int numSize = 0;
    int curPos = 0;
    long long curNum = 0x7fffffff;
    while (curPos < sufSize){
        while (isdigit(suf[curPos])){
            if (curNum == 0x7fffffff) curNum = 0;
            curNum = curNum * 10 + suf[curPos++] - '0';
        }
        if (suf[curPos] == '#') ++curPos;
        if (curNum != 0x7fffffff){
            numStack[numSize++] = curNum;
            curNum = 0x7fffffff;
        }
        if (isdigit(suf[curPos]))
            continue;
        Opt curOpt(suf[curPos++]);
        long long opr1 = 0, opr2 = 0;
        switch(curOpt.getOpt()){
        case '+': case '-': case '*': case '/': case '^':
            if (numSize < 2) throw runtime_error("fuck it");
            opr2 = numStack[--numSize];
            opr1 = numStack[--numSize];
            numStack[numSize++] = operate(opr1, opr2, curOpt);
            break;
        case '&': case '|':
            if (numSize < 1) throw runtime_error("fuck it");
            if (curOpt.getOpt() == '|')
                numStack[numSize - 1] = -numStack[numSize - 1];
            break;
        default:
            throw runtime_error("fuck it");
            break;
        }
    }
    return numStack[0];
}

int main(){
    try{
        infToSuf();
    }
    catch(runtime_error){
        cout << "Error" << endl;
        return 0;
    }
    try{
        cout << calcSuf() << endl;
    }
    catch(runtime_error){
        cout << "Error" << endl;
        return 0;
    }
    return 0;
}

q4x3's solution

/**
 * 计算器
 * longlong
 * 不判-1 1 0会超时
 * -1 ^ 2 = 1 (这就尼玛离谱)
 * 脑子有病的一个题
 **/
#include <iostream>
#include <stdio.h>

using namespace std;

struct stk {
    char dat[233];
    int top;
};
struct istk {
    long long dat[233];
    int top;
};

char tot[233], tmp;
char pre, cur;
long long cnt, head, flag = 1;
int main() {
    while(1) {
        tmp = getchar();
        if(tmp == ' ') continue;
        if(tmp == '\n') {
            tot[cnt ++] = 0;
            break;
        } else {
            tot[cnt ++] = tmp;
        }
    }
    stk tok;
    istk num;
    tok.top = -1;
    num.top = -1;
    while(1) {
        if(head + 1 == cnt) break;
        pre = cur;
        cur = tot[head ++];
        if(cur > '9' || cur < '0') {
            if(cur == '-') {
                if(pre == 0 || pre == '(' || pre == '*' || pre == '/' || pre == '^' || pre == '+' || pre == '-') {
                    tok.dat[++ tok.top] = '|';
                } else {
                    while(tok.top != -1 && tok.dat[tok.top] != '(') {
                        long long tmp1 = num.dat[num.top - 1], tmp2 = num.dat[num.top];
                        if(tok.dat[tok.top] == '+') {
                            num.dat[num.top - 1] = tmp1 + tmp2;
                            -- num.top;
                            -- tok.top;
                        } else 
                        if(tok.dat[tok.top] == '-') {
                            num.dat[num.top - 1] = tmp1 - tmp2;
                            -- num.top;
                            -- tok.top;
                        } else
                        if(tok.dat[tok.top] == '*') {
                            num.dat[num.top - 1] = tmp1 * tmp2;
                            -- num.top;
                            -- tok.top;
                        } else
                        if(tok.dat[tok.top] == '/') {
                            if(tmp2 == 0) {
                                cout << "Error" << endl;
                                return 0;
                            } else {
                                num.dat[num.top - 1] = tmp1 / tmp2;
                                -- num.top;
                                -- tok.top;
                            }
                        } else
                        if(tok.dat[tok.top] == '^') {
                            long long tmp = 1;
                            for(int i = 0;i < tmp2;++ i) {
                                if(tmp1 == 0) {
                                    tmp = 0;
                                    break;
                                } else if(tmp1 == 1) {
                                    tmp = 1;
                                    break;
                                } else if(tmp1 == -1) {
                                    if(tmp2 % 2 == 0)
                                        tmp = 1;
                                    else tmp = -1;
                                    break;
                                }
                                tmp *= tmp1;
                            }
                            num.dat[num.top - 1] = tmp;
                            -- num.top;
                            -- tok.top;
                        } else
                        if(tok.dat[tok.top] == '|') {
                            num.dat[num.top] = - num.dat[num.top];
                            -- tok.top;
                        }
                    }
                    tok.dat[++ tok.top] = '-';
                }
            } else
            if(cur == '(') {
                tok.dat[++ tok.top] = '(';
            } else
            if(cur == ')') {
                while(tok.top != -1 && tok.dat[tok.top] != '(') {
                    long long tmp1 = num.dat[num.top - 1], tmp2 = num.dat[num.top];
                    if(tok.dat[tok.top] == '+') {
                        num.dat[num.top - 1] = tmp1 + tmp2;
                        -- num.top;
                        -- tok.top;
                    } else 
                    if(tok.dat[tok.top] == '-') {
                        num.dat[num.top - 1] = tmp1 - tmp2;
                        -- num.top;
                        -- tok.top;
                    } else
                    if(tok.dat[tok.top] == '*') {
                        num.dat[num.top - 1] = tmp1 * tmp2;
                        -- num.top;
                        -- tok.top;
                    } else
                    if(tok.dat[tok.top] == '/') {
                        if(tmp2 == 0) {
                            cout << "Error" << endl;
                            return 0;
                        } else {                                
                            num.dat[num.top - 1] = tmp1 / tmp2;
                            -- num.top;
                            -- tok.top;
                        }
                    } else
                    if(tok.dat[tok.top] == '^') {
                        long long tmp = 1;
                        for(int i = 0;i < tmp2;++ i) {
                            if(tmp1 == 0) {
                                tmp = 0;
                                break;
                            } else if(tmp1 == 1) {
                                tmp = 1;
                                break;
                            } else if(tmp1 == -1) {
                                if(tmp2 % 2 == 0)
                                    tmp = 1;
                                else tmp = -1;
                                break;
                            }
                            tmp *= tmp1;
                        }
                        num.dat[num.top - 1] = tmp;
                        -- num.top;
                        -- tok.top;
                    }
                    if(tok.dat[tok.top] == '|') {
                        num.dat[num.top] = - num.dat[num.top];
                        -- tok.top;
                    }
                }
                if(tok.dat[tok.top] != '(') {
                    cout << "Error" << endl;
                    return 0;
                } else {
                    -- tok.top;
                }
            } else
            if(cur == '^') {
                while(tok.top != 1 && tok.dat[tok.top] == '|') {
                    num.dat[num.top] = - num.dat[num.top];
                    -- tok.top;
                }
                tok.dat[++ tok.top] = '^';
            } else
            if(cur == '*') {
                while(tok.top != -1 && tok.dat[tok.top] != '(' && tok.dat[tok.top] != '+' && tok.dat[tok.top] != '-') {
                    long long tmp1 = num.dat[num.top - 1], tmp2 = num.dat[num.top];
                    if(tok.dat[tok.top] == '*') {
                        num.dat[num.top - 1] = tmp1 * tmp2;
                        -- num.top;
                        -- tok.top;
                    } else
                    if(tok.dat[tok.top] == '/') {
                        if(tmp2 == 0) {
                            cout << "Error" << endl;
                            return 0;
                        } else {                                
                            num.dat[num.top - 1] = tmp1 / tmp2;
                            -- num.top;
                            -- tok.top;
                        }
                    } else
                    if(tok.dat[tok.top] == '^') {
                        long long tmp = 1;
                        for(int i = 0;i < tmp2;++ i) {
                            if(tmp1 == 0) {
                                tmp = 0;
                                break;
                            } else if(tmp1 == 1) {
                                tmp = 1;
                                break;
                            } else if(tmp1 == -1) {
                                if(tmp2 % 2 == 0)
                                    tmp = 1;
                                else tmp = -1;
                                break;
                            }
                            tmp *= tmp1;
                        }
                        num.dat[num.top - 1] = tmp;
                        -- num.top;
                        -- tok.top;
                    } else
                    if(tok.dat[tok.top] == '|') {
                        num.dat[num.top] = - num.dat[num.top];
                        -- tok.top;
                    }
                }
                tok.dat[++ tok.top] = '*';
            } else
            if(cur == '/') {
                while(tok.top != -1 && tok.dat[tok.top] != '(' && tok.dat[tok.top] != '+' && tok.dat[tok.top] != '-') {
                    long long tmp1 = num.dat[num.top - 1], tmp2 = num.dat[num.top];
                    if(tok.dat[tok.top] == '*') {
                        num.dat[num.top - 1] = tmp1 * tmp2;
                        -- num.top;
                        -- tok.top;
                    } else
                    if(tok.dat[tok.top] == '/') {
                        if(tmp2 == 0) {
                            cout << "Error" << endl;
                            return 0;
                        } else {                                
                            num.dat[num.top - 1] = tmp1 / tmp2;
                            -- num.top;
                            -- tok.top;
                        }
                    } else
                    if(tok.dat[tok.top] == '^') {
                        long long tmp = 1;
                        for(int i = 0;i < tmp2;++ i) {
                            if(tmp1 == 0) {
                                tmp = 0;
                                break;
                            } else if(tmp1 == 1) {
                                tmp = 1;
                                break;
                            } else if(tmp1 == -1) {
                                if(tmp2 % 2 == 0)
                                    tmp = 1;
                                else tmp = -1;
                                break;
                            }
                            tmp *= tmp1;
                        }
                        num.dat[num.top - 1] = tmp;
                        -- num.top;
                        -- tok.top;
                    } else
                    if(tok.dat[tok.top] == '|') {
                        num.dat[num.top] = - num.dat[num.top];
                        -- tok.top;
                    }
                }
                tok.dat[++ tok.top] = '/';
            } else
            if(cur == '+') {
                while(tok.top != -1 && tok.dat[tok.top] != '(') {
                    long long tmp1 = num.dat[num.top - 1], tmp2 = num.dat[num.top];
                    if(tok.dat[tok.top] == '+') {
                        num.dat[num.top - 1] = tmp1 + tmp2;
                        -- num.top;
                        -- tok.top;
                    } else 
                    if(tok.dat[tok.top] == '-') {
                        num.dat[num.top - 1] = tmp1 - tmp2;
                        -- num.top;
                        -- tok.top;
                    } else
                    if(tok.dat[tok.top] == '*') {
                        num.dat[num.top - 1] = tmp1 * tmp2;
                        -- num.top;
                        -- tok.top;
                    } else
                    if(tok.dat[tok.top] == '/') {
                        if(tmp2 == 0) {
                            cout << "Error" << endl;
                            return 0;
                        } else {                                
                            num.dat[num.top - 1] = tmp1 / tmp2;
                            -- num.top;
                            -- tok.top;
                        }
                    } else
                    if(tok.dat[tok.top] == '^') {
                        long long tmp = 1;
                        for(int i = 0;i < tmp2;++ i) {
                            if(tmp1 == 0) {
                                tmp = 0;
                                break;
                            } else if(tmp1 == 1) {
                                tmp = 1;
                                break;
                            } else if(tmp1 == -1) {
                                if(tmp2 % 2 == 0)
                                    tmp = 1;
                                else tmp = -1;
                                break;
                            }
                            tmp *= tmp1;
                        }
                        num.dat[num.top - 1] = tmp;
                        -- num.top;
                        -- tok.top;
                    } else
                    if(tok.dat[tok.top] == '|') {
                        num.dat[num.top] = - num.dat[num.top];
                        -- tok.top;
                    }
                }
                tok.dat[++ tok.top] = '+';
            }
        } else {
            if(pre > '9' || pre < '0')
                num.dat[++ num.top] = cur - '0';
            else {
                long long tmpi = num.dat[num.top];
                tmpi = tmpi * 10 + cur - '0';
                num.dat[num.top] = tmpi;
            }
        }
    }
    while(tok.top != -1) {
        if(tok.dat[tok.top] == '(') {
            cout << "Error" << endl;
            return 0;
        }
        long long tmp1 = num.dat[num.top - 1], tmp2 = num.dat[num.top];
        if(tok.dat[tok.top] == '+') {
            num.dat[num.top - 1] = tmp1 + tmp2;
            -- num.top;
            -- tok.top;
        } else 
        if(tok.dat[tok.top] == '-') {
            num.dat[num.top - 1] = tmp1 - tmp2;
            -- num.top;
            -- tok.top;
        } else
        if(tok.dat[tok.top] == '*') {
            num.dat[num.top - 1] = tmp1 * tmp2;
            -- num.top;
            -- tok.top;            
        } else
        if(tok.dat[tok.top] == '/') {
            if(tmp2 == 0) {
                cout << "Error" << endl;
                return 0;
            } else {                                
                num.dat[num.top - 1] = tmp1 / tmp2;
                -- num.top;
                -- tok.top;
            }
        } else
        if(tok.dat[tok.top] == '^') {
            long long tmp = 1;
            for(int i = 0;i < tmp2;++ i) {
                if(tmp1 == 0) {
                    tmp = 0;
                    break;
                } else if(tmp1 == 1) {
                    tmp = 1;
                    break;
                } else if(tmp1 == -1) {
                    if(tmp2 % 2 == 0)
                        tmp = 1;
                    else tmp = -1;
                    break;
                }
                tmp *= tmp1;
            }
            num.dat[num.top - 1] = tmp;
            -- num.top;
            -- tok.top;
        } else
        if(tok.dat[tok.top] == '|') {
            num.dat[num.top] = - num.dat[num.top];
            -- tok.top;
        }
    }
    cout << num.dat[num.top] << endl;
    //cout << "Error" << endl;
    return 0;
}

victrid's solution

#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
//EXCEPTIONS
struct ENOB {};
struct EDIV {};

struct atoma {
    //value:
    // 1 2 3 4 5  6
    // + - * / ^ (-)
    //priority level:
    // 00111000
    //    |-----------  + - = 1, * / = 2 ^ = 3 - = 4
    //        |-------- number of digit. (^ in 999-ans)
    //   |-------------- bracketcount
    bool isoperator;
    long long value;
    int priority;
};
atoma ps[100];
atoma zero{0, 0, 0};
struct tree {
    atoma& at;
    tree* left;
    tree* right;
    tree(atoma& a, tree* l, tree* r) : at(a), left(l), right(r){};
    ~tree() {
        if (left != nullptr)
            delete left;
        if (right != nullptr)
            delete right;
    }
};
int read() {
    char ch = 0;

    int
        chcount    = 0,
        bracket    = 0,
        atomaplace = 0,
        digit      = 0;

    long long totalis = 0;
    while (true) {
        if (ch < '0' || ch > '9') {
            if (digit) {
                ps[atomaplace++] = atoma{false, totalis, 0};
            }
            digit   = 0;
            totalis = 0;
            switch (ch) {
            case '+':
                ps[atomaplace++] = atoma{true, 1, bracket * 100000 + 10000 + 1000 - chcount};
                break;
            case '-':
                if (atomaplace == 0 || ps[atomaplace - 1].isoperator) {
                    ps[atomaplace++] = atoma{true, 6, bracket * 100000 + 40000 + 1000 - chcount};
                } else
                    ps[atomaplace++] = atoma{true, 2, bracket * 100000 + 10000 + 1000 - chcount};
                break;
            case '*':
                ps[atomaplace++] = atoma{true, 3, bracket * 100000 + 20000 + 1000 - chcount};
                break;
            case '/':
                ps[atomaplace++] = atoma{true, 4, bracket * 100000 + 20000 + 1000 - chcount};
                break;
            case '^':
                ps[atomaplace++] = atoma{true, 5, bracket * 100000 + 30000 + chcount};
                break;
            case '(':
                bracket++;
                break;
            case ')':
                if (bracket == 0)
                    throw(ENOB());
                bracket--;
                break;
            case '\n':
                //!!!!!!I'm too foolish!
                if (bracket != 0)
                    throw(ENOB());
                return atomaplace;
            default:
                break;
            }
            ch = getchar();
            chcount++;
        } else {
            digit++;
            totalis = totalis * 10 + (ch - '0');
            ch      = getchar();
            chcount++;
        }
    }
}
tree* search(int left, int right) {
    if (left > right)
        return new tree(zero, nullptr, nullptr);
    if (left == right)
        return new tree(ps[left], nullptr, nullptr);
    int min = 1e9;
    int loc = -1;
    for (int i = left; i <= right; i++) {
        if (ps[i].priority != 0 && ps[i].priority < min) {
            loc = i;
            min = ps[i].priority;
        }
    }
    tree* lf = search(left, loc - 1);
    tree* rt = search(loc + 1, right);
    return new tree(ps[loc], lf, rt);
}

long long integerpow(long long base, long long power) {
    long long ans = 1, tmp = base;
    while (power > 0) {
        if (power & 1)
            ans *= tmp;
        power >>= 1;
        tmp *= tmp;
    }
    return ans;
}

tree* shorten(tree* root) {
    if (!root->at.isoperator) {
        return root;
    }
    shorten(root->left);
    shorten(root->right);
    switch (root->at.value) {
    case 1:
        root->at.value = root->left->at.value + root->right->at.value;
        break;
    case 2:
        root->at.value = root->left->at.value - root->right->at.value;
        break;
    case 3:
        root->at.value = root->left->at.value * root->right->at.value;
        break;
    case 4:
        if (root->right->at.value == 0)
            throw(EDIV());
        root->at.value = root->left->at.value / root->right->at.value;
        break;
    case 6:
        root->at.value = root->left->at.value - root->right->at.value;
        break;
    case 5:
        if (root->right->at.value == 0)
            throw(EDIV());
        root->at.value = integerpow(root->left->at.value, root->right->at.value);
        break;
    }
    root->at.isoperator = false;
    root->at.priority   = 0;
    delete root->left;
    delete root->right;
    root->left  = nullptr;
    root->right = nullptr;
    return root;
}

int main() {
    int atomacount;
    try {
        atomacount = read();
    } catch (ENOB) {
        cout << "Error" << endl;
        return 0;
    }
    tree* lg = search(0, atomacount - 1);
    try {
        cout << shorten(lg)->at.value << endl;
    } catch (EDIV) {
        cout << "Error" << endl;
        return 0;
    }
    return 0;
}