C++ 利用栈解决运算问题-白红宇的个人博客

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

发布日期：2022-04-02 18:15:31 浏览次数：7 分类：博客文章

本文共 2401 字，大约阅读时间需要 8 分钟。

2017-06-27 19:19:18

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

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

数字直接输出

"("直接进栈

")"将栈中元素出栈直到遇到"("

其他运算符需要和栈顶元素比较优先级，如果栈顶元素的优先级小于等于待操作的运算符的，则需要出栈并输出。直到栈顶元素的优先级大于待处理元素

最后需要将栈中元素清空，全部输出

int toint(string in){    int rst;    stringstream ss;    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
     
      & vec){     stack
      
        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
       
        & vec){    stack
        
          s;    for(int i=0;i
         
           vec; midtopost(in,vec); cout<
          
           <

转载地址：https://www.cnblogs.com/hyserendipity/p/7086302.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：使用递归和非递归遍历二叉树

下一篇：C++ 多态性和虚函数

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章