题解 | #四则运算#

写个小解释器进行计算

#include <iostream>
#include <vector>
using namespace std;

/*EBNF Grammar

<Expression> := <MulDiv_Expression>{"+"|"-" <MulDiv_Expression>}
<MulDiv_Expression> := <Primary_Expression>{"+"|"-" <Primary_Expression>}
<Primary_Expression> := NUM | "-"NUM | "("<Expression>")"

*/

//Token
enum TokenType
{
    NUM,
    PLUS,MINUS,
    MUL,DIV,
    LEFT,RIGHT
};

class Token
{
public:
    TokenType type;
    int value;
    Token(TokenType type):type(type){}
    Token(TokenType type,int value):type(type),value(value){}
};

vector<Token>tokens;


//Scanner
void Scan(string str)
{
    for(int begin=0;begin<str.size();)
    {
        if(isdigit(str[begin]))
        {
            int end=begin;
            while(end<str.size()&&isdigit(str[end]))end++;
            tokens.push_back(Token(NUM,stoi(str.substr(begin,end-begin))));
            begin=end;
        }
        else
        {
            switch(str[begin])
            {
                case '+':tokens.push_back(PLUS);break;
                case '-':tokens.push_back(MINUS);break;
                case '*':tokens.push_back(MUL);break;
                case '/':tokens.push_back(DIV);break;
                case '(':case '[':case '{':tokens.push_back(LEFT);break;
                case ')':case ']':case '}':tokens.push_back(RIGHT);break;
            }
            begin++;
        }
    }
}


//To help interpreter
int current=0;
bool match(TokenType type)
{
    if(tokens[current].type==type)
    {
        current++;
        return true;
    }
    return false;
}

//Interpreter
int Interpret_Expression();

int Interpret_PrimaryExpression()
{   
    int value;
    if(match(NUM))value=tokens[current-1].value;
    else if(match(MINUS))
    {
        value=-tokens[current].value;
        match(NUM);
    }
    else 
    {
        match(LEFT);
        value=Interpret_Expression();
        match(RIGHT);
    }
    return value;
}

int Interpret_MulDivExpression()
{
    int value=Interpret_PrimaryExpression();
    while(match(MUL)||match(DIV))
    {
        if(tokens[current-1].type==MUL)
        {
            value*=Interpret_PrimaryExpression();
        }
        else {
            value/=Interpret_PrimaryExpression();
        }
    }
    return value;
}

int Interpret_Expression()
{
    int value=Interpret_MulDivExpression();
    while(match(PLUS)||match(MINUS))
    {
        if(tokens[current-1].type==PLUS)
        {
            value+=Interpret_MulDivExpression();
        }
        else {
            value-=Interpret_MulDivExpression();
        }
    }
    return value;
}


int main() {
    string str;cin>>str;
    Scan(str);

    cout<<Interpret_Expression();

    return 0;
}