算法训练 表达式计算 (中缀表达式转后缀表达式)

问题描述
　　输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。
输入格式
　　输入一行，包含一个表达式。
输出格式
　　输出这个表达式的值。
样例输入
1-2+3*(4-5)
样例输出
-4
数据规模和约定
　　表达式长度不超过100，表达式运算合法且运算过程都在int内进行。

http://lx.lanqiao.cn/problem.page?gpid=T419

#include<iostream>
#include<algorithm>
#include<string>
#include<cctype>
#include<stack>
#include<cstdio>
#include<vector>
#include<fstream>
#include<ctime>
#include<queue> 
#define ALL(x) x.begin(),x.end()
using namespace std;

string s1;
queue<string> q1;
stack<string> stk1;
stack<int> stk2;

int f2(string s)
{
    if(s=="+") return 2;
    else if(s=="-") return 2;
    else if(s=="*") return 3;
    else if(s=="/") return 3;

    
}

void f1()
{
    string temp;
    cin>>s1;
    for(int i=0;i<s1.size();++i)
    {
        temp.clear();
        if(isdigit(s1[i]))
        {
            while(i<s1.size()&&isdigit(s1[i]))
            {
                temp+=s1[i];
                ++i;
            }
            --i;
            q1.push(temp);
        }
        else
        {
            temp+=s1[i];
            if(temp=="(")
            {
                stk1.push(temp);
            }
            else if(temp==")")
            {
                while(!stk1.empty()&&stk1.top()!="(")
                {
                    q1.push(stk1.top());
                    stk1.pop();
                }
                stk1.pop();             
            }
            else if(!stk1.empty()&&f2(temp)>f2(stk1.top()))
            {
                stk1.push(temp);
            }
            else
            {
                while(!stk1.empty()&&f2(temp)<=f2(stk1.top()))
                {
                    q1.push(stk1.top());
                    stk1.pop();
                }
                stk1.push(temp);
            }
            
        }
        
    }
    while(!stk1.empty())
    {
        q1.push(stk1.top());
        stk1.pop();
    }
    return ;
}

void f3()
{
    int temp=0,x,y;
    while(!q1.empty())
    {
        temp=0;
        string s1=q1.front();
        if(s1.size()>1)
        {
            for(int j=0;j!=s1.size();++j)
            {
                temp=temp*10+(s1[j]-'0');
            }
            stk2.push(temp);
        }
        else if(isdigit(s1[0]))
        {
            temp=s1[0]-'0';
            stk2.push(temp);
        }
        else
        {
            if(s1=="+")
            {
                y=stk2.top();
                stk2.pop();
                x=stk2.top();
                stk2.pop();
                stk2.push(x+y);
            }
            else if(s1=="-")
            {
                y=stk2.top();
                stk2.pop();
                x=stk2.top();
                stk2.pop();
                stk2.push(x-y);
            }
            else if(s1=="*")
            {
                y=stk2.top();
                stk2.pop();
                x=stk2.top();
                stk2.pop();
                stk2.push(x*y);
            }
            else if(s1=="/")
            {
                y=stk2.top();
                stk2.pop();
                x=stk2.top();
                stk2.pop();
                stk2.push(x/y);
            }
        }
        q1.pop();
    }
}
int main()
{
    f1();
//  while(!q1.empty())
//  {
//      cout<<q1.front();
//      q1.pop();
//  }
//  cout<<endl;
    f3();
    cout<<stk2.top();

    return 0;
    
}