表达式求值

1. 中缀表达式转后缀表达式

机算中缀转后缀然后使用栈直接计算后缀表达式

弹出所有优先级高于或等于当前的

2. 直接计算中缀表达式

1表示top的操作符 后放入同级的操作符应输出大于

在栈顶和最后加上 # 代表开头和结束的

char Procede(char a, char b) {
    char priority[6][6] = {
        {'>','>','<','<','<','>'},
        {'>','>','<','<','<','>'},
        {'>','>','>','>','<','>'},
        {'>','>','>','>','<','>'},
        {'>','>','>','>','>','>'},
        {'<','<','<','<','<','='}
    };
    int i, j;
    switch (a) {
    case'+':i = 0; break;
    case'-':i = 1; break;
    case'*':i = 2; break;
    case'/':i = 3; break;
    case'^':i = 4; break;
    case'#':i = 5; break;   // # 是表达式的结束符 
    }
    switch (b) {
    case'+':j = 0; break;
    case'-':j = 1; break;
    case'*':j = 2; break;
    case'/':j = 3; break;
    case'^':j = 4; break;
    case'#':j = 5; break;
    }
    return priority[i][j];
}

int Operate(int m, int n, char x) {
    if (x == '+')
        return m + n;
    if (x == '-')
        return n - m;
    if (x == '*')
        return m * n;
    if (x == '/')
        return n / m;
    if (x == '^')
    {
        int j;
        int ans = 1;
        for (j = 0; j < m; j++)
        {
            ans =ans * n;
        }
        return ans;
    }
}

int main()
{
    char str[100],ss[2] = "#";
    cin >> str;
    stack<int> OPND;
    stack<char> OPTR;
    char c = str[0];
    int k = 0;
    int N = 0;
    for (int i = 0; i < 100; i++)
    {
        if (str[i] != '\0')
        {
            N++;
        }
        else
        {
            break;
        }
    }
    str[N] = '#';
    str[++N] = '\0';
    while( c!='#' || OPTR.top()!='#')
    {
        if (k == 0)
        {
            OPTR.push('#');
        }
        c = str[k];
        if (c >= '0' && c <= '9')
        {
            OPND.push(c - '0');
            k++;
        }
        else
        {
            char J = Procede(OPTR.top(), c);
            switch (J)
            {
            case'<': {OPTR.push(c); k++;} // 当前比栈顶的大就 push 
            case'=': break; 
            case'>': {char x = OPTR.top(); OPTR.pop(); // 如果小于说明栈顶的可以开始计算
                      int m = OPND.top(); OPND.pop();
                      int n = OPND.top(); OPND.pop();
                      OPND.push(Operate(m, n, x)); 
                     }

            }
        }
    }
    cout << OPND.top();
}

https://blog.csdn.net/qq_41317652/article/details/82958188

有括号版本，规则一样，运算符比栈顶高优先就进，比栈顶低就运算栈顶。当遇到 ( 和 ) 比较的时候直接抛出符号栈内的 ( 这样就解决了括号问题

char Procede(char a, char b) {
    char priority[8][8] = {
    {'>','>','<','<','<','>','>','<'},
    {'>','>','<','<','<','>','>','<'},
    {'>','>','>','>','<','>','>','<'},
    {'>','>','>','>','<','>','>','<'},
    {'<','<','<','<','<','=','0','<'},  
    {'>','>','>','>','0','>','>','<'},
    {'<','<','<','<','<','0','=','<'},
    {'>','>','>','>','<','>','>','>'}

};                              
    int i, j;
    switch (a) {
        case'+':i = 0; break;
        case'-':i = 1; break;
        case'*':i = 2; break;
        case'/':i = 3; break;
        case'(':i = 4; break;
        case')':i = 5; break;
        case'#':i = 6; break;
        case'^':i = 7; break;
    }
    switch (b) {
        case'+':j = 0; break;
        case'-':j = 1; break;
        case'*':j = 2; break;
        case'/':j = 3; break;
        case'(':j = 4; break;
        case')':j = 5; break;
        case'#':j = 6; break;
        case'^':j = 7; break;
    }
    return priority[i][j];
}

int Operate(int m, int n, char x) {
    if (x == '+')
        return m + n;
    else if (x == '-')
        return n - m;
    else if (x == '*')
        return m * n;
    else if (x == '/')
        return n / m;
    else if (x == '^')
    {
        int j;
        int ans = 1;
        for (j = 0; j < m; j++)
            {
                ans =ans * n;
            }
        return ans;
    }
}

int main()
{
    char str[1000];
    cin >> str;
    stack<long> OPND;
    stack<char> OPTR;
    char c = str[0];
    int k = 0;
    int N = 0;
    for (int i = 0; i < 1000; i++)
        {
            if (str[i] != '\0')
            {
                N++;
            }
            else
            {
                break;
            }
        }
    str[N] = '#';
    str[++N] = '\0';
    c = str[k];
    while (c != '#' || OPTR.top() != '#')
        {
            if (k == 0)
            {
                OPTR.push('#');
            }
            if (c >= '0' && c <= '9')
            {
                int y = 0;
                while (c >= '0' && c <= '9') {   // 用while可读取超过一位数字
                    y = y * 10 + (c - '0');
                    if (k + 1 <= N)
                    {
                        c = str[++k];
                    }
                    else
                    {
                        break;
                    }
                }
                OPND.push(y);
            }
            else
            {
                char J = Procede(OPTR.top(), c);
                switch (J)
                    {
                        case'<': {OPTR.push(c); k++;  break; }
                        case'=': {OPTR.pop(); k++; break; }
                        case'>': {char x = OPTR.top(); OPTR.pop();
                                  int m = OPND.top(); OPND.pop();
                                  int n = OPND.top(); OPND.pop();
                                  OPND.push(Operate(m, n, x));
                                  break;
                                 }
                        case'0':break;
                    }
            }
            c = str[k];     //c直接到下一位
        }
    cout << OPND.top();
}