Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

测试数据通过了,为什么一直WA

Posted by qq1205470086 at 2015-05-02 17:03:41 on Problem 1400
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator