把带括号的一般正常的算式,转换成逆波兰式。
输入和输出如下例子:
Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))
Output:
abc*+
ab+zx+*
at+bac++cd+^*
总结规律是很困难的事情,总结好就能很快解决:
1 字母直接放结果
2 ‘(’入栈
3 ‘)’ 出栈到‘(’,然后出栈‘(’
4 操作符比较,高优先级的全部出栈,入结果,操作符入栈
#include <iostream>
#include <string>
#include <queue>
#include <stack>
using namespace std;
int opToint(char op)
{
if ('+' == op) return 0;
if ('-' == op) return 1;
if ('*' == op) return 2;
if ('/' == op) return 3;
if ('^' == op) return 4;
return -1;
}
bool cmpOP(char a, char b)
{
return opToint(a) - opToint(b) < 0;
}
string handleRPN(string &express)
{
string ans;
stack<char> stk;
for (int i = 0; i < express.size(); i++)
{
if ('a' <= express[i] && express[i] <= 'z') ans.push_back(express[i]);
else if ('(' == express[i]) stk.push(express[i]);
else if (')' == express[i])
{
while (!stk.empty() && '(' != stk.top())
{
ans.push_back(stk.top());
stk.pop();
}
if (!stk.empty() && '(' == stk.top()) stk.pop();
}
else
{
while (!stk.empty() && '(' != stk.top() &&
!cmpOP(stk.top(), express[i]) )
{
ans.push_back(stk.top());
stk.pop();
}
stk.push(express[i]);
}
}
return ans;
}
void TransformTheExpressionToRPN()
{
string express;
int T = 0;
cin>>T;
while (T--)
{
cin>>express;
cout<<handleRPN(express)<<endl;
}
}
分享到:
相关推荐
SPOJ-Solutions:SPOJ算法问题的解决方案
杨弋SPOJ做题表格
Haskell 中的 Spoj 算法
spoj reverse 的solution
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
Online Judge Problem solution VN.SPOJ
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...
My solution for some spoj problems
RandomCode:Python算法,SPOJ,涂鸦
cp:一些SPOJ问题的解决方案
SPOJ( )上选定问题的解决方案
SPOJ-备份工具 介绍 在 Sphere Online Judge ( ) 中,您可以尝试所给的具有挑战性的问题。 它还使您能够查看和下载您自己的解决方案。 工具 SPOJ_BACKUP 备份所有已接受的提交并将它们保存在脚本所在的计算机位置。...
联系 Python中SPOJ问题的解决方案。
分机检查spoj用户的排名。 此扩展名有2个选项: - 在选择的比赛中显示用户排名 - 在选择比赛中最多可比较5个用户第一个在后台运行,并在每隔几分钟内更新,您可以设置自己(并默认为15分钟)。当您单击分机的徽标时...
spoj MSTS kruskal +生成树
检查SPOJ用户等级的扩展名。 这个扩展有两个选项: - 在选择比赛中显示用户等级 - 比较最多5个用户选择比赛 第一个在后台运行,每隔几分钟更新一次,您可以自己设置(默认为15分钟)。 第二个是当你点击分机的标志...
gcd(a,b)= d (d为素数,1,1)