I. Discussion on Principles

In fact, if we want to clarify compiling principles and other things, the first step is to do lexical analysis, with lexical analysis, we can do grammatical analysis. I discuss a small example of simple lexical analysis - arithmetic expression. This is a question that one of my netizens asked me, although I have a general idea, either using stack model or using binary tree model. But the idea is not very clear, it took some time to sort out the idea and form the code. The train of thought is as follows:

1. We need to separate each data, for example: 3 * 2.3 + 2, that is, 3, *, 2.3, +, 2.
2. With a single data, we change it from infix to suffix expression, 3, 2.3,*, 2,.+
3. With suffix expressions, we can use stack properties to calculate values.

The first problem is better solved. The second one is how to turn it around. What about brackets? It seems troublesome, but the essence is regular. The rules are as follows:

1. If the top() priority of symbol stack is higher than the current traversal symbol, go out of the stack and enter the current traversal symbol into the stack.
2. Encounter (`left parentheses, symbol stack remains unchanged, and Add'(`on the stack').
3.Encounter')'Right bracket, symbol stack has been out of the stack until encounter'('left bracket').

2. Upper Code

After analyzing the above principle, we can write a trial code. Because of the lack of optimization, the code may not be very concise, but it is sufficient to analyze the principles.

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;
enum AnalysisType:unsigned char{FLOAT=0x01,OPERATOR=0x02};
struct ItemValue
{
    union ValueUnion
    {
        float fdigit;
        char symbol;
    };
    AnalysisType type;
    ValueUnion value;
};
//Simple int addition, subtraction, multiplication and division
int GetPriority(char symbol)
{
    switch (symbol)
    {
    case '+':
    case '-':
        return 0;
    case '*':
    case '/':
        return 1;
    case '(':
    case ')':
        return 2;
    }
    return -1;
}

bool IsOperator(char symbol)
{
    switch (symbol)
    {
        case '+':
        case '-':
        case '*':
        case '/':
        case '(':
        case ')':
        return true;
    }
    return false;
}
//Converting to vector Storage
void wordsAnalysis(char*pIn, vector<ItemValue>&vec)
{
    int nCount = strlen(pIn);
    int nIndex = 0;
    while (nIndex<nCount)
    {
        ItemValue item = { FLOAT,0};
//Processing operator
        if (IsOperator(pIn[nIndex]))//If it is an operator
        {
            item.type = OPERATOR;
            item.value.symbol = pIn[nIndex];
            vec.push_back(item);
        }
//Processing numbers
        int nTemp = nIndex;
        char nBuffer[20] = {0};//20 place
        while (isdigit(pIn[nTemp]) || '.'==pIn[nTemp])
        {   
            nBuffer[nTemp - nIndex]=pIn[nTemp];
            ++nTemp;
        }
        if (nTemp != nIndex)
        {
            item.value.fdigit = atof(nBuffer);
            vec.push_back(item);
        }
//////////
        if (nTemp != nIndex)
            nIndex += strlen(nBuffer);
        else
            ++nIndex;
    }
}
//Interfix to suffix
void midToLast(vector<ItemValue> & vecIn, vector<ItemValue> & vecOut)
{
    ItemValue item{ OPERATOR ,0.0f };
    stack<char> stack_symbol;
    for_each(std::begin(vecIn), std::end(vecIn), [&](ItemValue &it) {
        if (FLOAT == it.type )
        {
            vecOut.push_back(it);
        }
        else if (OPERATOR == it.type)
        {
            if (')' == it.value.symbol)
            {
                while (!stack_symbol.empty())
                {
                    if (stack_symbol.top() == '(')
                    {
                        stack_symbol.pop();
                        return;
                    }
                    item.value.symbol = stack_symbol.top();
                    stack_symbol.pop();
                    vecOut.push_back(item);
                }
            }
            if (!stack_symbol.empty())
            {
                if (GetPriority(stack_symbol.top()) - GetPriority(it.value.symbol) >= 0 && stack_symbol.top()!='(')
                {
                    item.value.symbol = stack_symbol.top();
                    stack_symbol.pop();
                    vecOut.push_back(item);
                }
            }
            if(')' != it.value.symbol)
                stack_symbol.push(it.value.symbol);
        }
    });
    //Put up the operators in the stack
    while (!stack_symbol.empty())
    {
        item.value.symbol = stack_symbol.top();
        stack_symbol.pop();
        vecOut.push_back(item);
    }
}
//Calculation
float Calculate(vector<ItemValue>& vec)
{
    float fResult=0.0f;
    stack<ItemValue> stack_value;
    for_each(std::begin(vec), std::end(vec), [&](ItemValue &it) {
        if (FLOAT == it.type)
        {
            stack_value.push(it);
        }
        else if(OPERATOR == it.type)
        {
            ItemValue Value1, Value2 ;
            Value2=stack_value.top();
            stack_value.pop();

            Value1=stack_value.top();
            stack_value.pop();

            switch (it.value.symbol)
            {
            case '+':
                Value1.value.fdigit += Value2.value.fdigit;
                break;
            case '-':
                Value1.value.fdigit -= Value2.value.fdigit;
                break;
            case '*':
                Value1.value.fdigit *= Value2.value.fdigit;
                break;
            case '/':
                Value1.value.fdigit /= Value2.value.fdigit;
                break;
            }
            Value1.type = FLOAT;
            stack_value.push(Value1);
        }
    });
    fResult = stack_value.top().value.fdigit;
    return fResult;
}

int main()
{
    char buffer[64] = {0};
    vector<ItemValue> vecIn,vecOut;
    cout << "Please enter an expression:";
    cin >> buffer;
    wordsAnalysis(buffer, vecIn);//Split data
    midToLast(vecIn,vecOut);//Go to the suffix expression, vecOut
    cout << "Interfix to suffix:";
    for_each(std::begin(vecOut), std::end(vecOut), [&](ItemValue &it) {
        FLOAT == it.type?       
        cout << it.value.fdigit << "  ":
        cout << (char)it.value.symbol << "  ";
    });
    cout <<endl<<"The results are as follows:" << Calculate(vecOut)<<endl ;
    return 0;
}

3. Successful operation:

More articles: http://blog.csdn.net/what951006?viewmode=list
powered by: the little turtle is on the back of the big turtle~