Time Limit: 1000MS
Memory Limit: 65536KB
Submit
Statistic
Discuss
Problem Description
对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。
Input
输入一个算术表达式，以‘#’字符作为结束标志。
Output
输出该表达式转换所得到的后缀式。
Example Input
a*b+(c-d/e)*f#
Example Output
ab*cde/-f*+
Hint
Author
这是修改版，受到OJ题目判定的影响，第一个版本的代码有很大的漏洞就AC了，现在补上第二版。
本题使用栈的方法，请想找用二叉树解决的出门右转。
关键点就是对运算符号优先级的判断。我们用一个字符串来储存最终的结果，用栈来暂时储存运算符号。
首先，遇到字母直接进入字符串，遇到运算符号：
1.栈空时，直接进栈。
2.当运算符号的优先级大于栈顶元素时，进栈。
3.当运算符号的优先级小于等于栈顶元素时，栈顶元素出栈，直到优先级变化或空栈；
4.左括号进栈，右括号把左右括号中间元素出栈
这是第一版代码，错误原因是当运算符号的优先级相同时处理错误
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;
const int maxn = 1000;
int main()
{
stack<char> s1, s2;
char str[maxn];
char houzhui[maxn];
cin>>str;
int i, n;
n = strlen(str);
for(i = 0; i < n; i++)
{
if(str[i]=='#')
break;
if(str[i] >= 'a' && str[i] <= 'z')
{
s1.push(str[i]);
}
else if(str[i] == '(' || str[i] == '*' || str[i] == '/')
{
s2.push(str[i]);
}
else if(str[i] == '+' || str[i] == '-')
{
if(!s2.empty()) //当栈为空时empty返回1，否则返回0，一定不要搞混；
{
while((s2.top()=='*'||s2.top()=='/'))
{
s1.push(s2.top());
s2.pop();
if(s2.empty()) //当栈为空时就不可进行pop、top操作，否则会报错；
break;
}
s2.push(str[i]);
}
}
else if(str[i] == ')')
{
while(s2.top()!='(')
{
s1.push(s2.top());
s2.pop();
}
s2.pop();
}
}
while(!s2.empty())
{
s1.push(s2.top());
s2.pop();
}
n = s1.size();
for(i = 0; i < n; i++)
{
houzhui[i] = s1.top();
s1.pop();
}
for(i = n-1; i >= 0; i--)
{
cout<<houzhui[i];
}
return 0;
}
这是修改版
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;
const int maxn = 1000;
int main()
{
stack<char> s1, s2;
char str[maxn];
char houzhui[maxn];
cin>>str;
int i, n;
n = strlen(str);
for(i = 0; i < n; i++)
{
if(str[i]=='#')
break;
if(str[i] >= 'a' && str[i] <= 'z')
{
s1.push(str[i]);
}
else if(str[i] == '(')
{
s2.push(str[i]);
}
else if(str[i] == '*' || str[i] == '/')
{
if(!s2.empty())
while(s2.top()=='*'||s2.top()=='/')
{
s1.push(s2.top());
s2.pop();
if(s2.empty())
break;
}
s2.push(str[i]);
}
else if(str[i] == '+' || str[i] == '-')
{
if(!s2.empty())
{
while(s2.top()=='*'||s2.top()=='/'||s2.top() == '+'||s2.top() == '-')
{
s1.push(s2.top());
s2.pop();
if(s2.empty())
break;
}
}
s2.push(str[i]);
}
else if(str[i] == ')')
{
while(s2.top()!='(')
{
s1.push(s2.top());
s2.pop();
}
s2.pop();
}
}
while(!s2.empty())
{
s1.push(s2.top());
s2.pop();
}
n = s1.size();
for(i = 0; i < n; i++)
{
houzhui[i] = s1.top();
s1.pop();
}
for(i = n-1; i >= 0; i--)
{
cout<<houzhui[i];
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-25060.html
