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