1.7.1 right and wrong problem (infix expression)

1.7.1 Right and wrong questions

Description

uncle-lu Fascinated by logical value operations . but uncle-lu My head is dizzy , I haven't figured out why . He had to find you , Let you help him solve the problem .

Input

A string ( The string length is less than 255255255) Express logical formula , Only true,false,or,and,not And Spaces ,( Do not include brackets and xor), The priority is the same as pascal.(not->and->or), The left side of the same level is counted first , If the logic formula is wrong, output error.

Output

Calculation results ：true perhaps false , If you can't get the output of the result error

Sample Input 1

true or false and false

Sample Output 1

true

analysis ：

1) It is based entirely on expressions , Without the help of other advanced data structures ;
    map Containers can be initialized with multiple values using curly braces ;
    And operator , Non operator operation , The final result is only the or operator , As long as there is one stored value
    yes 1, The final result is true;

/**
    1) It is based entirely on expressions , Without the help of other advanced data structures ;
    map Containers can be initialized with multiple values using curly braces ;
     And operator , Non operator operation , The final result is only the or operator , As long as there is one stored value 
     yes 1, The final result is true;
*/


#include <iostream>
#include <cstdio>
#include <map>
using namespace std;

int main()
{
    map<string,int>mp{
   {"false",0},{"true",1},{"or",2},{"and",3},{"not",4}};
    string str;
    getline(cin,str);
    int a[100],index=0;
    string temp;
    int len=str.size();
    int pre=10,cou=0,err=0;   //pre Store the value of the last character 
    int first=-1,second=-1; //first And second They are the two operators of and operation 
    for(int i=0,j=0,l=0;i<len;)
    {
        l=0;
        while(i<len&&isspace(str[i]))
            ++i;
        j=i;    //j Is the starting position of a character 
        while(i<len&&!isspace(str[i++]))
            ++l;    // The length of this character 
        temp=str.substr(j,l);   // Take a character 
        int flag=mp[temp];
        if(flag>=0&&flag<=1) //err Record the number of consecutive values , An expression greater than or equal to two is an error 
            ++err;
        if(flag>=2&&flag<=3)
            err=0;  // As long as you have && or || Operator , Will err Turn into 0;
        if(pre<2&&flag==2)
        {
            a[index++]=pre; // If the previous character is a numeric value and the current character is an or operation , Directly store the previous value in ;

        }
        else if(err==2||(pre>=2&&pre<=3||pre==4||pre==10)&&(flag>=2&&flag<=3))
        {
            printf("error");    // If the previous character is && or ||, The next character is && or || Or the first one 
            return 0;           // The character is && or ||, Then this expression is wrong 
        }
        else if(flag==3)
            first=pre;  // If this operator is &&,, It will be && The previous value is assigned to first, So that we can calculate later 
        else if(pre==4&&(flag>=0||flag<=1)) // If the previous operator is the inverse operator and the current operator is a number 
        {
            if(cou%2==1)    //cou Record the number of non operators 
                flag=(flag+1)%2;
            cou=0;
            if(first==-1)
                first=flag;
            else
                second=flag;
        }
        else if(flag==4)    //cou Record the number of non operators 
            ++cou;
        else if(first!=-1&&second==-1&&(flag>=0||flag<=1))
            second=flag;
        if(first!=-1&&second!=-1)
        {
            int tem=first*second;
            a[index++]=tem;
            first=second=-1;
            pre=tem;
            continue;   // If it is an and operation , Then assign the operation result to pre
        }
        pre=flag;   // As long as the current is not participation and operation , Then assign the current operator to pre
        if(i==len-1)    // This step is necessary , Otherwise, it will enter the dead cycle 
            break;
    }
    int res=0;
    for(int i=0;i<index;++i)
    {
        if(a[i]==1)
            res=1;
    }

    if(res)
        printf("true\n");
    else
        printf("false\n");
    return 0;
}

The following code is written by someone else's blog ：

http://t.csdn.cn/W1yn8

2) Infix expression ：
    Store data and symbols on two stacks respectively ; Input a character and save one , When symbols are stored ,
    Compare whether the top symbol element of the symbol stack has higher priority than the current symbol , If it is , Then calculate the previous
    data , Store it again .
    cin >> str; When the end of the file is reached ,cin return EOF, So it can be used while(cin >> str ) To input
    Do not know the number of text

/**
    2) Infix expression ：
     Store data and symbols on two stacks respectively ; Input a character and save one , When symbols are stored ,
     Compare whether the top symbol element of the symbol stack has higher priority than the current symbol , If it is , Then calculate the previous 
     data , Store it again .
    cin >> str; When the end of the file is reached ,cin return EOF, So it can be used while(cin >> str ) To input 
     Do not know the number of text 
*/

/**
#include <cstdio>
#include <iostream>
using namespace std;

const int maxn =256;
int data[maxn]={0},sign[maxn]={0};
int top_d=0,top_s=0;
void pop();
int main()
{
    string str;
    while(cin >> str)
    {
        if(str=="true")
            data[++top_d]=1;
        else if(str=="false")
            data[++top_d]=0;
        else if(str=="or")
        {
            //if(top_s)
            while(top_s) // Only... Can be used here while, They can't be used if, Because when there are many not When , If you use if
                pop();   // sentence , Then it will lead to the first few not Operate with the result of the following operation , And in itself not
            sign[++top_s]=1;    // It should be the reverse operation with the following number , Result in an error 
        }
        else if(str=="and")
        {
            //if(top_s&&sign[top_s]>=2)
            while(top_s&&sign[top_s]>=2)// As long as the stack is not empty and the operator priority at the top of the stack is not lower than and, Just calculate 
                pop();
            sign[++top_s]=2;    // After the stack top operator operation is completed , Put this operator on the stack 
        }
        else
            sign[++top_s]=3;
    }
    while(top_s)
        pop();

    if(top_d==1)    // As long as the expression is correct , Then finally data The stack has only one element 
        cout << boolalpha << (bool)data[top_d] <<  endl;  //boolalpha  Only to bool Type 
    else
        cout << "error\n";
    return 0;
}

void pop()
{
    int temp=sign[top_s];
    switch(temp)  //switch Statement has braces 
    {
        case 1: //case There's a colon in the back 
            if(top_d<2)
            {
                printf("error\n");
                exit(0);
            }
            data[top_d-1]=data[top_d-1]||data[top_d];
            --top_d;
            break;
        case 2:
            if(top_d<2)
            {
                printf("error\n");
                exit(0);
            }
            data[top_d-1]=data[top_d-1]&&data[top_d];
            --top_d;
            break;
        case 3:
            data[top_d]=!data[top_d];
            break;
    }
    --top_s;
}
*/