UOJ Logo lris的博客

博客

#69/71[计算/中缀表达式]题解(换一道题换了两个字符qwq)

2018-02-23 03:37:12 By lris

即建立一个运算符栈,一个数栈,先处理掉所有的负号(优先级最高),特判括号。

当且仅当栈顶运算符优先级低于新运算符时,新运算符进栈。

注意我这里有错误,为了方便将乘方与负号优先级设为相等,毕竟两道题不一样233.

talk is cheap, show me the code=v=

#include<iostream>
#include<cstdio>
#include<stack>
#include<cmath>
#include<cctype>
using namespace std;
stack<int> num;
stack<char> ope;
string s;
int len, flag, innum;
int priority(char c)
{
    if(c=='$' || c=='^')    return 3;
    if(c=='*' || c=='/')    return 2;
    if(c=='+' || c=='-')    return 1;
    else                    return 0;
}
bool isope(char c)              //judge the argue
{
    switch(c)
    {
        case '+':case '-':case '*':case '/': return 1;
        default: return 0;
    }
}
int pre_the_expression()         //preperation expression
{
    cin>>s;
    len=s.length()-1;            //the last question you should change the length
    int pos=-1;
    while((pos=s.find('-', pos+1))!=string::npos)
        if(priority(s[pos-1]) || s[pos-1]=='(' || pos==0) s[pos]='$';
    for(int i=1; i<len; i++)
        if(isope(s[i]) && isope(s[i+1])) return 1;
    return 0;
}
void pop_num()
{
    char c=ope.top(); ope.pop();
    int n1=num.top(); num.pop();
    if(c=='$') num.push(n1*-1);  //single ope
    else 
    {
        int n2=num.top(); num.pop();
        switch(c)
        {
        case '+': num.push(n2+n1); break;
        case '-': num.push(n2-n1); break;
        case '*': num.push(n2*n1); break;
        case '/': num.push(n2/n1); break;
        case '^': num.push(pow(n2, n1)); break; 
        }
    }
}
int main()
{
    //freopen("in.txt", "r", stdin);
    if(pre_the_expression())    //too many opes
    {                            
        printf("NO");
        return 0;
    }
    for(int i=0; i<len; i++)    //work
    {
        if(isdigit(s[i]))                                    //digit
        {
            innum=s[i]-'0';
            while(isdigit(s[i+1]))
            {
                i++;
                innum=innum*10+s[i]-'0';
            }    
            num.push(innum);
            continue;
        }        
        else if(s[i]=='(') ope.push('(');
        else if(s[i]==')')                                   //()
        {
            while(ope.top()!='(' && !ope.empty())
                pop_num();                                    //wrong ()
            if(ope.empty()) {flag=1;break;}
            else ope.pop();
        }
        else                                                  //the opes
        {
            while(!ope.empty() && priority(s[i])<=priority(ope.top()))
                pop_num();
            ope.push(s[i]);
        }
    }
    while(!ope.empty())    pop_num();
    if(flag)    printf("NO");
    else        printf("%d", num.top());
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。