【表达式转换 (25 分)】
题目分析
首先规定优先级，括号为最高优先级，乘号或除号为次优先级，加或减号为最低优先级，至于数字，碰到就直接输出即可。 既然是数字，就有小数，整数，正数，负数之分，还有关于二元运算符的输出，在括号内的二元运算符优先输出，优先级高的优先输出（当然括号不算啊） 根据题意，在输出时可分为以下几种情况。
- (+1......
- +1...... 对于正号，是不能输出的
- -1......
- 3
- 34...
- 3.4... （注意：上面的...指一堆未知长度的数字）
- 碰到 ）符号，将与它对应的括号这之间的符号从栈内导出，也就是输出它们。 上面几种情况只讨论了部分输出问题，下面讨论向栈中插入二元运算符。
- 当栈为空或者栈顶运算符的优先级小于当前二元运算符的优先级时，将该二元运算符导入。
- 倘若栈顶运算符的优先级大于或等于当前二元运算符的优先级，又分为以下两种情况，1.若栈顶运算符为（ 符号，则直接将该运算符插入即可； 2.若栈顶运算符不是（ 符号，则优先输出栈内的元素,直到碰到（ 符号或者栈为空，然后将当前二元运算符插入。
正确代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
using namespace std;
stack<char> sign;
char s[22];
map<char, int> 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<iostream>
#include<stack>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
stack<int> num;
stack<char> oper;
map<char, int> 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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-09-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录