# 【表达式转换 (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;
}```

0 条评论

• ### Artwork (Gym - 102346A)【DFS、连通块】

1.这道题就是让你判断从(0,0)到(m,n)，避开中途所有的传感器(传感器的检测范围为半径为s的圆)的检测区域，最终能否到达(m,n)。

• ### sendRedirect()和forward()方法的区别

虽然二者都可以实现获取相应的url资源，但首先要注意的是，重定向由sendRedirect来实现，请求转发由forward来实现。

• ### 直播卖货小程序源码中，商品分类页面是如何实现的

在直播卖货小程序源码中，一般都包含商品分类页面，如下图，那么这个页面是如何通过代码实现的呢？下面，小编以iOS版本的开发过程为例，来讲述下实现过程。

• ### 据说这里可以帮你解决许多关于WebView的问题

使用WebView开发的坑很多，这是众所周知的。本文分别对WebView的三个基本控件（俗称三剑客WebViewClient，WebChromeClient,W...

• ### Android -- 真正的 高仿微信 打开网页的进度条效果

(本博客为原创，https://cloud.tencent.com/developer/user/1148436/activities) 目录： 　　一，为什么...

• ### 邓侃：中国首个全过程智能诊疗系统，全方位披露技术核心和商业模式

演讲嘉宾：邓侃 【新智元导读】新智元AI WORLD 2017 世界人工智能大会，大数医达CEO、CMU计算机学院暨机器人研究所博士邓侃，发表演讲《智能诊断系统...

• ### NetScaler 固件升级到11.1版本后管理员界面无法登陆

最近做了一次Citrix平台的整体升级，由底层XS、应用层XD、XM、PVS访问层NetScaler，在升级Netscaler由10.5到11.1的过程中，出现...

• ### 如何定制一款12306抢票浏览器——用户界面

我不打算写个Windows界面。因为这个软件的全部就是个浏览器。我准备将”浏览器“进行到底，所以我选择使用html作为我们的用户界面。我也并不打...