计算器(中缀表达式转后缀表达式）
问题 G: 计算(calc)
时间限制: 1 Sec 内存限制: 128 MB提交: 8 解决: 3
[提交][状态][讨论版]
题目描述
小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)
输入
共1行，为一个算式。
输出
共1行，就是密码。
样例输入
1+(3+2)*(7^2+6*9)/(2)
样例输出
258
#include<iostream>#include<string.h>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<queue>
#include<map>
#include<stack>
#include<string.h>
#include<string>
using namespace std;
stack<long long> P;
stack<char> Q;
int yy(char t)//判断优先级
{
if(t=='+'||t=='-')return 1;
if(t=='*'||t=='/')return 2;
if(t=='^')return 3;
if(t=='(')return -1;//虽然"("的优先级大，但是只有遇到")"时才能取出
}
long long pow1(long long a,long long b)
{
long long r=1;
for(long long i=1;i<=b;i++)
r=r*a;
return r;
}
void yunsuan(char t)
{
long long x=P.top();P.pop();long long y=P.top();P.pop();
if(t=='+')P.push(y+x);
if(t=='-')P.push(y-x);
if(t=='*')P.push(y*x);
if(t=='/')P.push(y/x);
if(t=='^')P.push(pow1(y,x));
}
int main()
{
char t[10000];
scanf("%s",&t);
int L=strlen(t);
for(int i=0;i<L;i++)
{
if(t[i]>='0'&&t[i]<='9')
{
long long m=0;
for(int j=i;;j++)
{
if(j>=L||!(t[j]>='0'&&t[j]<='9'))
{
i=j-1;break;
}
m=m*10+t[j]-'0';
}
P.push(m);
}//字符串转整形
else
{
if(Q.empty())Q.push(t[i]);
else if(t[i]=='(')Q.push(t[i]);//栈为空或字符为"("直接放
else
{
if(t[i]==')')
{
while(1)
{
char q=Q.top();
Q.pop();if(q=='(')break;
yunsuan(q);//每取出运算符进行一次运算
}
}
else
{
while(!Q.empty()&&yy(Q.top())>=yy(t[i]))//取出之前优先级大于等于该运算符的运算符
{
yunsuan(Q.top());
Q.pop();
}
Q.push(t[i]);
}
}
}
}
while(!Q.empty())
{
yunsuan(Q.top());
Q.pop();
}
printf("%lld",P.top());
return 0;
}