【表达式转换 (25 分)】-白红宇

【表达式转换 (25 分)】

阅读量：4966 次

发布时间：2019-06-12

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

题目分析

首先规定优先级，括号为最高优先级，乘号或除号为次优先级，加或减号为最低优先级，至于数字，碰到就直接输出即可。

既然是数字，就有小数，整数，正数，负数之分，还有关于二元运算符的输出，在括号内的二元运算符优先输出，优先级高的优先输出（当然括号不算啊）

根据题意，在输出时可分为以下几种情况。

(+1......

+1...... 对于正号，是不能输出的

-1......

34...

3.4...
（注意：上面的...指一堆未知长度的数字）

碰到）符号，将与它对应的括号这之间的符号从栈内导出，也就是输出它们。
上面几种情况只讨论了部分输出问题，下面讨论向栈中插入二元运算符。

当栈为空或者栈顶运算符的优先级小于当前二元运算符的优先级时，将该二元运算符导入。

倘若栈顶运算符的优先级大于或等于当前二元运算符的优先级，又分为以下两种情况，1.若栈顶运算符为（符号，则直接将该运算符插入即可； 2.若栈顶运算符不是（符号，则优先输出栈内的元素,直到碰到（符号或者栈为空，然后将当前二元运算符插入。

正确代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          using namespace std;stack
           
             sign;char s[22];map
            
              mp;int main(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); mp['+'] = mp['-'] = 1; mp['*'] = mp['/'] = 2; mp['('] = mp[')'] = 3; scanf("%s", s); int len = strlen(s); bool isfirst = true; for(int i = 0; i < len; i++) { if((!i || (i && s[i-1] == '(')) && (s[i] == '+' || s[i] == '-')) { if(!isfirst) printf(" "); if(s[i] != '+') printf("%c",s[i]); while(i + 1 < len && (s[i+1] == '.' || (s[i+1] >= '0' && s[i+1] <= '9'))) { ++i; printf("%c", s[i]); } if(isfirst) isfirst = false; } else if(s[i] >= '0' && s[i] <= '9') { if(!isfirst) printf(" "); printf("%c", s[i]); while(i + 1 < len && (s[i+1] == '.' || (s[i+1] >= '0' && s[i+1] <= '9'))) { ++i; printf("%c", s[i]); } if(isfirst) isfirst = false; } else if(s[i] == ')') { while(!sign.empty() && sign.top() != '(') { printf(" %c", sign.top()); sign.pop(); } if(!sign.empty() && sign.top() == '(') sign.pop(); } else if(sign.empty() || (mp[s[i]] > mp[sign.top()])) sign.push(s[i]); else { while(!sign.empty() && sign.top() != '(') { printf(" %c", sign.top()); sign.pop(); } sign.push(s[i]); } } while(!sign.empty()) { printf(" %c", sign.top()); sign.pop(); }}

扩展

关于这道题，如果让你输出这个表达式的值，可以这样做。

安排两个栈，分别存数字和符号，具体要求如下。（该程序还有欠缺，目前对带正号的正数以及小数不支持，只支持正常的整数混合运算）

#include
    
     #include
     
      #include
      
       #include
       
        #include
        using namespace std;stack
         
           num;stack
          
            oper;map
           
             mp;char s[22];void solve(int a, int b, char o){ int c; if(o == '+') c = a + b; else if(o == '-') c = a - b; else if(o == '*') c = a * b; else if(o == '/') c = a / b; if(o != ')') num.push(c);}int main(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); scanf("%s", &s); int len = strlen(s); mp['('] = mp[')'] = 0; mp['+'] = mp['-'] = 1; mp['*'] = mp['/'] = 2; for(int i = 0; i < len; i++) { if(s[i] >= '0' && s[i] <= '9') num.push(s[i] - '0'); else { if(oper.empty() || mp[oper.top()] < mp[s[i]] || s[i] == '(') oper.push(s[i]); else { if(mp[oper.top()] == mp[s[i]]) { int b = num.top() ; num.pop(); int a = num.top() ; num.pop(); solve(a, b, oper.top()); oper.pop(); oper.push(s[i]); } else if(mp[oper.top()] > mp[s[i]]) { if(s[i] == ')') { while(!oper.empty() && mp[oper.top()] > mp[s[i]]) { int b = num.top() ; num.pop(); int a = num.top() ; num.pop(); solve(a, b, oper.top()); oper.pop(); } if(oper.top() == '(') oper.pop(); } else { while(!oper.empty() && mp[oper.top()] >= mp[s[i]]) { int b = num.top() ; num.pop(); int a = num.top() ; num.pop(); solve(a, b, oper.top()); oper.pop(); } oper.push(s[i]); } } } } } while(!oper.empty()) { int b = num.top() ; num.pop(); int a = num.top() ; num.pop(); solve(a, b, oper.top()); oper.pop(); } cout << num.top() << endl;}

转载于:https://www.cnblogs.com/KeepZ/p/11563413.html

你可能感兴趣的文章