数据结构实验之栈二：一般算术表达式转换成后缀式
Time Limit: 1000MS Memory Limit: 65536KB
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; }
京公网安备 11010502036488号