| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
测试数据通过了,为什么一直WA#include <string>
#include <stack>
#include <map>
#include <iostream>
using namespace std;
bool isNum(char c){
return (c >= 'a' && c <= 'z');
}
map<char, int> priority_infix;
map<char, int> priority_sufix;
//中缀转后缀
void InfixToSuffix(const char* source, string& result){
result.clear();
string sou(source), res, str;
stack<char> st;
int len = strlen(source);
for (int i = 0; i < len; ++i){
char c = source[i];
if (isNum(c)) result.append(&c, 1);
else if (c == ')'){
while (st.top() != '('){ result.append(&st.top(),1); st.pop(); }
st.pop();
}
else if (c == '(') st.push(c);
else{
if (!st.empty() && priority_infix[st.top()] >= priority_infix[c]){ result.append(&st.top(),1); st.pop(); }
st.push(c);
}
}
while (!st.empty()){ result.append(&st.top(),1); st.pop(); }
}
typedef struct EXP{
string e;
int op;
EXP(string e) : e(e), op(0x7fffffff){}
EXP(string e, int op) : e(e), op(op){}
}EXP;
//后缀转中缀
void SuffixToInfix(const char* source, string& result){
stack<EXP> st;
string sou(source), res, str, tmp1, tmp2;
int len = strlen(source);
for (int i = 0; i < len; ++i){
char c = source[i];
if (isNum(c)) {
string str;
str.assign(&c, 1);
st.push(str);
}
else{
if (st.top().op < priority_sufix[c] || ((st.top().op == priority_sufix[c]) && (c == '-' || c == '/'))) tmp2 = "(" + st.top().e + ")";
else tmp2 = st.top().e;
st.pop();
if (st.top().op < priority_sufix[c]) tmp1 = "(" + st.top().e + ")";
else tmp1 = st.top().e;
st.pop();
tmp1.append(&c, 1);
tmp1 += tmp2;
EXP exp(tmp1, priority_sufix[c]);
st.push(exp);
}
}
result.assign(st.top().e);
}
int main(){
priority_infix['+'] = 1; priority_infix['-'] = 2; priority_infix['*'] = 3; priority_infix['/'] = 4;
priority_sufix['+'] = 1; priority_sufix['-'] = 1; priority_sufix['*'] = 2; priority_sufix['/'] = 2;
string str, suffix, infix;
int t;
cin >> t;
while (t--){
cin >> str;
InfixToSuffix(str.c_str(), suffix);
SuffixToInfix(suffix.c_str(), infix);
cout << infix << endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator