C++ 利用栈解决运算问题

2017-06-27 19:19:18

第一步需要将中缀表达式转为后缀表达式。这步的转化可以说是本题的核心。

主要的转化手段是利用栈，有如下几个规则：

• 数字直接输出
• "("直接进栈
• ")"将栈中元素出栈直到遇到"("
• 其他运算符需要和栈顶元素比较优先级，如果栈顶元素的优先级小于等于待操作的运算符的，则需要出栈并输出。直到栈顶元素的优先级大于待处理元素
• 最后需要将栈中元素清空，全部输出

int toint(string in)
{
    int rst;
    stringstream ss;
    ss<<in;
    ss>>rst;
    return rst;
}

int priority(char a)
{
    switch(a)
    {
    case '*': return 2;
    case '/': return 2;
    case '+': return 1;
    case '-': return 1;
    case '(': return 3;
    case ')': return 3;
    }
}

bool isdig(char a)
{
    if(a>='0'&&a<='9') return true;
    else return false;
}

//保证每次入栈的符号的优先级都比当前的栈顶元素要高，若此时栈顶的优先级比入栈元素低或者等于的话，则需要出栈
//知道遇到比当前需要入栈元素优先级高的为止
void midtopost(string in,vector<string>& vec)
{
     stack<char> s;
     string rst="";
     int i=0;
     while(true)
     {     
         if(i>=in.length()) break;
         if(isdig(in[i]))
         {
             string num="";
             while(isdig(in[i])) num+=in[i++];
             vec.push_back(num);
         }
         else
         {
             if(s.empty()) s.push(in[i++]);
             else
             {
                 if(in[i]=='(') {s.push(in[i]);}
                 else if(in[i]==')')
                 {
                     while(s.top()!='(') 
                     {
                         string temp="";
                         temp+=s.top();
                         vec.push_back(temp);
                         s.pop();
                     }
                     s.pop();
                 }
                 else
                 {
                     if(priority(in[i])>priority(s.top())||s.top()=='(') s.push(in[i]);
                     else
                     {
                         //判断是否为空必须写在前面，符合短路原则
                         while(!s.empty()&&(priority(in[i])<=priority(s.top())))
                         {
                             string temp="";
                             temp+=s.top();
                             vec.push_back(temp);
                             s.pop();
                         }
                         s.push(in[i]);
                     }
                 }
                 ++i;
             }

         }
     }
     //清空栈
     while(!s.empty())
     {
         string temp="";
         temp+=s.top();
         vec.push_back(temp);
         s.pop();
     }
}

//后缀表达式的计算，数字进栈，符号将栈顶两个元素出栈，运算后进栈
int calc(vector<string>& vec)
{
    stack<int> s;
    for(int i=0;i<vec.size();++i)
    {
        if(!vec[i].compare("*"))
        {
            int x=s.top();
            s.pop();
            int y=s.top();
            s.pop();
            s.push(x*y);
        }
        else if(!vec[i].compare("-"))
        {
            int x=s.top();
            s.pop();
            int y=s.top();
            s.pop();
            s.push(y-x);
        }
        else if(!vec[i].compare("+"))
        {
            int x=s.top();
            s.pop();
            int y=s.top();
            s.pop();
            s.push(x+y);
        }
        else if(!vec[i].compare("/"))
        {
            int x=s.top();
            s.pop();
            int y=s.top();
            s.pop();
            s.push(y/x);
        }
        else
        {
            s.push(toint(vec[i]));
        }
    }
    return s.top();
}

int main()
{ 
    string in="9+(3-1)*3+10/2";
    //string s="9 3 1 - 3 * + 10 2 / +";
    vector<string> vec;
    midtopost(in,vec);
    cout<<calc(vec)<<endl;
    return 0; 
}