1358：中缀表达式值(expr)

题目网址：信息学奥赛一本通（C++版）在线评测系统

题目介绍：

1358：中缀表达式值(expr)

时间限制: 1000 ms         内存限制: 65536 KB
提交数:13372    通过数: 4646

【题目描述】

输入一个中缀表达式（由0-9组成的运算数、加+减-乘*除/四种运算符、左右小括号组成。注意“-”也可作为负数的标志，表达式以“@”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请把表达式转换成后缀形式，再求出后缀表达式的值并输出。

注意：必须用栈操作，不能直接输出表达式的值。

【输入】

一行为一个以@结束的字符串。

【输出】

如果表达式不合法，请输出“NO”，要求大写。

如果表达式合法，请输出计算结果。

【输入样例】

1+2*8-9@

【输出样例】

8

样例代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
const int N=10000+10;
using namespace std;
 
int n,m;
stack<int> s1;//操作数栈
stack<char> s2;//运算符栈
 
int level(char x)//运算符优先级
{
    if(x=='+'||x=='-')
        return 1;
    if(x=='*'||x=='/')
        return 2;
    if(x=='^')
        return 3;
    return 0;
}
 
void calc(stack<int> &s1,stack<char> &s2)//弹出栈顶元素并计算
{
    /*取出后弹出栈*/
    int y=s1.top();
        s1.pop();
    int x=s1.top();
        s1.pop();
    char z=s2.top();
        s2.pop();
 
    /*根据运算符计算,并压入栈*/
    if(z == '+')
        s1.push(x+y);
    if(z == '-')
        s1.push(x-y);
    if(z == '*')
        s1.push(x*y);
    if(z == '/')
        s1.push(x/y);
    if(z == '^')
        s1.push(pow(x,y));
}
 
int c(int x)
{
    return x != 0;
}
char str[1000000];
int sum[1000000];
 
int main(){
 
    scanf("%s",str+1);
    n = strlen(str+1)-1;//忽略掉@的字符串长度
 
    for(int i = 1;i <= n;i++)//检查匹配
    {
        sum[i] += sum[i-1];
        if(str[i] == '(')
            sum[i]++;
        if(str[i] == ')')
            sum[i]--;
    }
 
    bool out = false;
    for(int i = 2;i <= n;i++)
        if( c(level(str[i])) && c(level(str[i-1])) )
        {
            out = 1;
            break;
        }
 
    if( ( n==1 && c(level(str[1])) )||sum[n]||out )//表达式不合法
    {
        cout<<"NO"<<endl;
        return 0;
    }
 
    stack<int> s1;
    stack<char> s2;
    int temp = 0;
    bool flag = false;
    for(int i = 1 ;i <= n;i++)
    {
        if('0' <= str[i] && str[i] <= '9')//判断当前字符是否为数字
        {
            temp = (temp<<3)+(temp<<1)+str[i]-'0';
            flag = true;
        }
        else
        {
            if(flag)
            {
                s1.push(temp);
                temp = 0;
                flag = false;
            }
            if(str[i] == '(')
            {
                s2.push(str[i]);
                continue;
            }
            if(str[i] == ')')
            {
                while(s2.top()!='(')
                    calc(s1,s2);
                s2.pop();
                continue;
            }
            while(!s2.empty() && level(s2.top()) >= level(str[i]))//优先级判断
                calc(s1,s2);
            s2.push(str[i]);//运算符入栈
        }
    }
    if(flag)
    {
        s1.push(temp);
        temp = 0;
        flag = false;
    }
    while(!s2.empty())
        calc(s1,s2);
    cout << s1.top() << endl;
    return 0;
}