글 읽기 - 1918번 어떻게 맞으셨는지 궁금합니다.

pichulia 9년 전 3

A+B-C같은 경우는

AB+C-도,

ABC-+도 될 수 있습니다.

문제에선 이러한 경우에 대해 어떻게 처리해달라는 요구사항도 없었는데

데이터중에 저렇게 여러가지로 표현할 수 있는 데이터가 들어오고 있습니다.

이거 맞으신 분들은 어떤 규칙으로 후위연산자를 표시하셨나요?

참고로 저는 연산자중 먼저 등장한 연산자의 우선순위를 더 높게 줘서 풀었습니다.

#include<stdio.h>	
#include<string>
#include<algorithm>
using namespace std;
char buf[9999];
string dfs(string x)
{
	int i, j;
	string left,right,mid;
	left = right = mid = "";
	if(x.size() == 0) return x;
	if(x[0] == '(')
	{
		int cnt=0;
		for(i=1;;i++)
		{
			if(x[i] == '(')
				cnt++;
			else if(x[i]==')')
			{
				cnt--;
				if(cnt<0)
				break;
			}
			left += x[i];
		}
		i++;
		left = dfs(left);
	}
	else
	{
		left = x[0];
		i = 1;
	}
	if(i>=x.size()) return left;
	mid += x[i];
	i++;
	if(i < x.size())
		right = dfs(x.substr(i));
	return left+right+mid;
}
int main()
{
	scanf("%s",buf);
	int i, j, k;
    for(i=0;buf[i];i++)
    {
        if((buf[i]>='A'&&buf[i]<'Z')||buf[i]=='+'||buf[i]=='-'||buf[i]=='*'||buf[i]=='/'||buf[i]=='('||buf[i]==')')continue;
        for(i=2;i>0;i++)printf("%d\n",i);
    }
	string a = buf;
	for(i=0;i<a.size();i++)
	{
		if(a[i]=='*' || a[i]=='/')
		{
			int cnt=0;
			for(j=i-1;j>=0;j--)
			{
				if(a[j]==')')cnt++;
				else if(a[j]=='(')cnt--;
				else if(cnt==0 && (a[j] <'A' || a[j]>'Z')) break;
			}
			j++;
			string pre = a.substr(0,j);
			cnt=0;
			for(k=i+1;k<a.size();k++)
			{
				if(a[k]==')')cnt--;
				else if(a[k]=='(')cnt++;
				else if(cnt==0 && (a[k] <'A' || a[k]>'Z')) break;
			}
			string next = "";
			if(k<a.size())
			next = a.substr(k);
			string mid = a.substr(j,(k-j));
			a = pre + '(' +mid +')'+ next;
            i++;
		}
	}
	for(i=0;i<a.size();i++)
	{
		if(a[i]=='+' || a[i]=='-')
		{
			int cnt=0;
			for(j=i-1;j>=0;j--)
			{
				if(a[j]==')')cnt++;
				else if(a[j]=='(')cnt--;
				else if(cnt==0 && (a[j] <'A' || a[j]>'Z')) break;
			}
			j++;
			string pre = a.substr(0,j);
			cnt=0;
			for(k=i+1;k<a.size();k++)
			{
				if(a[k]==')')cnt--;
				else if(a[k]=='(')cnt++;
				else if(cnt==0 && (a[k] <'A' || a[k]>'Z')) break;
			}
			string next = "";
			if(k<a.size())
			next = a.substr(k);
			string mid = a.substr(j,(k-j));
			a = pre + '(' +mid +')'+ next;
            i++;
		}
	}
	string b = dfs(a);
	printf("%s\n",b.c_str());
}

WeissBlume 9년 전 0

전 교과서에 나온대로 짰는데, AB+C-가 나오네요.

+나 -를 만나면 stack에서 '('가 아닌 게 top인 동안은 쭉 뽑아주고,

*나 /를 만나면 stack에서 '+'니 '-'나 '('가 아닌게 top인 동안은 쭉 뽑아주고,

'('는 그냥 push, ')'은 stack에서 ')'가 top일 때까지 쭉 뽑았어요.

숫자는 그때그때 출력하고!

pichulia 9년 전 0

흠...제 코드는 교과서랑 별반 다를게 없는데...

왜 틀렸을까요?

제 코드가 틀렸을리는 없으니

제 코드가 내는 결과랑 정답이랑 다르게 표현되는 데어터로는 어떤게 있을까요?ㅠㅠㅠㅠ

혹시 AX+C 같이 숫자가 여러개의 문자로 이루어질 수 있나요?

pichulia 9년 전 0

흠...일단 여러개의 문자가 연속되서 등장하지는 않네요...

테스트케이스가 여러개인 것도 아니고....

역시 자살이 답인가요?

pichulia 9년 전 5

암 자가치료했습니다.

A+B를 (A+B)로 묶어주는 과정에서 문제가 생겼었었네요

수정된 부분의 코드도 첨가합니다. 이런 실수를 하는 사람이 있을진 모르겠지만

도움이 되기를...

                if(cnt==0)
                {
                    if(a[k]=='(')cnt++;
                    else if(a[k] <'A' || a[k]>'Z') break;
                }
                else
                {
				if(a[k]==')')cnt--;
				else if(a[k]=='(')cnt++;
                }

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1918번 어떻게 맞으셨는지 궁금합니다.

pichulia 9년 전 3

WeissBlume 9년 전 0

pichulia 9년 전 0

pichulia 9년 전 0

pichulia 9년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말