중위표기식을 후위표기식으로 변환시 식이 다르게 나오지만 결과값은 같은데 괜찮은지 알고싶습니다.

Sift의 이미지

안녕하세요 스텍을 공부하고있는 학생입니다.
중위표기수식을 후위표기로 바꾸는 프로그램을 만들었는데
모범답안과 식이 조금 다르게 나옵니다.

하지만 결과값은 동일한데 모범답안처럼 나오지 않는 이유와
모범답안의 후위표기식 처럼 값이 나오지는 않지만 제가짠 코드가 맞는지
후위표기식이 달라도 값이 같을수 있는지

이렇게 세가지 알고싶습니다.
또 비록 아직 많이 배운것이 없지만 어떻게하면 더 빠르거나 깔끔하게 더 좋은 모범적인 코딩을할수 있는지 알고싶습니다.
고수분들 도와주세요!

----------data.txt 에 입력되어 있는 값------------
(2+3)*4+9
(1+5)*(3-2)
5*2+3+(4-2)

---------모범답안 출력---------
23+4*9+
15+32-*
52*3+42-+ <-------------이녀석이 값이 다르게 나옵니다 아마도 괄호때문인것 같은데 결국 계산한 값은 같습니다.

--------아래 제가짠 코드의 답안 출력-----------
23+4*9+
15+32-*
52*342-++ <-------------이녀석이 값이 다르게 나옵니다 아마도 괄호때문인것 같은데 결국 계산한 값은 같습니다.

#include<stdio.h>
#include<Windows.h>
 
//Node 는 스텍에 들어있는 데이터로서 한개의 문자와 자신 다음의 노드를 가르키는 포인터 *Next를 가지고 있습니다.
struct Node
{
	char Data;
	struct Node *Next;
};
typedef struct Node Node;
 
//Stack 은 구조체로 연결리스트처럼 머리가있고 다음것을 가르킵니다 count는 스텍에 저장된 데이터 노드의 갯수입니다. head는 제일 마지막에 입력된 노드를 가르키는 포인터입니다.
struct Stack
{
	int count;
	Node *head;
};
typedef struct Stack Stack;
 
//Pop 함수는 Stack의 Head를 제거하며 제거되는 값을 return 시키고 Stack의 head와 count를 수정해주는 함수입니다.
char Pop(Stack *Temp)
{
	//head를 제거하기전에 head Node의 Next 주소값과 head의 데이터값을 저장해둡니다
	Node *Next = Temp->head->Next;
	char Data = Temp->head->Data;
 
	if(Temp->head != NULL)
	{
		//Stack 의 head를 free함수로 할당된 메모리를 제거합니다.
		free(Temp->head);
 
		//Stack 의 head를 위에 저장해둔 head 다음 노드로 교체합니다.
		Temp->head = Next;
 
		//Stack 의 count 값을 1 줄여줍니다. (노드를 한개 지웠기 때문에 갯수 1감소)
		Temp->count -= 1;
		return Data;
	}else
	{
		//Stack 의 head가 없을경우가 있기때문에 잘못 실행했을경우 오류를 출력하고 return 값을 0을 줍니다.
		printf("Stack의 Head가 비어있습니다.\n");
		return 0;
	}
}
 
//Push 함수는 Stack에 새로운 Node를 만들어 Data 값을 집어넣고 Stack의 head,count 값을 수정해주는 함수입니다.
void Push(Stack *Temp,char Data)
{
	//새로운 노드 생성
	Node *NewNode;
	NewNode = (Node*)malloc(sizeof(Node));
 
	//새로운 노드에 Data값 삽입 
	NewNode->Data = Data;
 
	//새로운 노드는 head가 되므로 새로운 노드의 Next값은 Temp의 head
	NewNode->Next = Temp->head;
 
	//Temp의 count 값을 올려줍니다.(새로운 노드가 추가되었기때문에 갯수 +1), Temp의 head는 마지막에 들어온 NewNode로 변경해줍니다.
	Temp->count += 1;
	Temp->head = NewNode;
}
 
//OpLevel 함수는 연산기호를 받아 어떤것이 우선순위인지 리턴해주는 함수입니다.
int OpLevel(char OP)
{
	switch(OP)
	{
	case '*': case '/':
		return 2;
	case '+': case '-':
		return 1;
	case '(': case ')':
		return 0;
	default:
		return -1;
	}
}
 
//메인함수
int main()
{
	//파일포인터 선언
	FILE *fp;
 
	//스텍 생성
	Stack *MainStack;
 
	//파일의 총 문자열이 얼마나 되는지 알아내기위해 count 변수 사용및, 반복문을위한 i 선언.
	int i,count;
 
	//파일에 들어있는 중위표기 수식을 저장할 Input 선언(문자열 크기를 모르므로 동적할당하기위해 포인터로 선언)
	//파일에 들어있는 데이터를 받아들일 Fdata변수 선언
	char *Input,Fdata;
 
	//스텍을 동적할당으로 생성및 초기화
	MainStack = (Stack*)malloc(sizeof(Stack));
	MainStack->count = 0;
 
	//초기 스텍은 비어있어 head가 없으므로 NULL 값 삽입.
	MainStack->head = NULL;
 
	//data.txt라는 파일을 읽기모드로 열음
	fp = fopen("data.txt","r");
 
	//문자열의 갯수를 알아내기위해 count값 초기화
	count = 0;
 
	//파일이 끝날때까지 반복하여 총 문자열이 몇개인지 알아내는 반복문입니다.
	//문자가 끝이 아닐경우 count값 증가, 다음문자 읽음
	while(fscanf(fp,"%c",&Fdata) != EOF)
	{
		count++;
	}
 
	//이제는 파일에 있는 문자를 제대로 읽기위하여 rewind함수로 파일포인터 위치 초기화 
	rewind(fp);
 
	//Input 변수를 count+1개만큼의 크기로 동적할당합니다. (마지막에 \0를 넣기위해 count+1개 만큼 동적할당 합니다.)
	Input = (char*)malloc(sizeof(char)*(count+1));
 
	//Input에 data.txt에 들어있는 중위표기수식을 일렬로 쭉 읽어들입니다.
	i=0;
	while(fscanf(fp,"%c",&Input[i]) != EOF)
	{
		i++;
	}
 
	//마지막에는 \0를 삽입하여 문자열의 끝을 알수있도록 합니다.
	Input[i] = '\0';
 
	//파일이 끝이 아닐때까지 문자를 불러들여와 중위표기수식 후위표기수식으로 바꿉니다.
	i=0;
	while(Input[i] != '\0')
	{
		//Input에 들어있는 값이 연산자인지 피연산자인지, 괄호인지 확인후 출력할지 스텍에 삽입할지 결정하기 위해 switch문을 사용합니다.
		switch(Input[i])
		{
			//* 나 / 연산자 일경우 우선순위가 제일 높기때문에 스텍에 Push를 이용해 새로운 노드로 삽입합니다.
		case '*': case'/':
			Push(MainStack,Input[i]);
			break;
			//+ 나 - 연산자 일경우 자신보다 우선순위가 높은연산자가 스텍에 삽입되어 있을경우 모두 Pop시킨후 Push합니다.
		case '+': case'-':
			//메인스텍이 비어있을경우 우선순위를 판가름하는 OpLevel 함수에서 오류가 나게될것이므로 스텍이 비어있는지 확인한후 실행합니다.
			if(MainStack->head != NULL)
			{
				//OpLevel 함수를 이용하여 연산자의 우선순위를 파악합니다.
				while(OpLevel(MainStack->head->Data) > OpLevel(Input[i]))
				{
					//Stack에 쌓여있는 Node의 값이 자신보다 연산순위가 높을경우 Pop시키며 출력합니다.
					printf("%c",Pop(MainStack));
 
					//이것도 마찬가지로 Pop시킨후 head값이 없을경우 OpLevel에서 오류가 나게되므로 head가 비었는지 확인후 비어있으면 반복문을 탈출하도록 합니다.
					if(MainStack->head == NULL)
					{
						break;
					}
				}
				//자신보다 우선순위가 높은 연산자들을 출력후 자신을 Push로 Stack에 집어넣습니다.
				Push(MainStack,Input[i]);
			}
			break;
		case '(':
			//괄호는 스텍에 바로 집어넣습니다.
			Push(MainStack,Input[i]);
			break;
		case ')':
			//괄호가 닫히게 될경우 괄호가 열렸던 시점까지의 연산자를 모두 Pop시키며 출력합니다.
			while(MainStack->head->Data != '(')
			{
				printf("%c",Pop(MainStack));
			}
			//반복문이 완료된후에도 Pop시키는 이유는 '('가 아직 스텍에 남아있기 때문입니다. '('도 제거하기위해 Pop을 시켰습니다.
			Pop(MainStack);
			break;
		case '\n':
			//한개의 중위표기수식이 읽혀졌을경우에는 Stack에 남아있는 값들을 모두 Pop시켜 Stack을 초기화 시켜줍니다. break를 사용하지 않은 이유는 default에서 \n이 자동으로 출력되어 줄바꿈하기 위함입니다.
			while(MainStack->count>0)
			{
				printf("%c",Pop(MainStack));
			}
		default:
			//자신이 연산자가 아니며,괄호도 아닌 피연산자일경우 출력합니다.(단 연산자, 피연산자와 괄호,\n만 입력되었다고 가정시)
			printf("%c",Input[i]);
			break;
		} 
		i++;
	}
 
	//모든 중위표기 수식을 읽어들여 변환후 마지막에 스텍에 남은값들을 모두 Pop시킵니다.
	while(MainStack->count>0)
	{
		printf("%c",Pop(MainStack));
	}
	printf("\n");
 
	system("pause");
	return 0;
}
익명 사용자의 이미지

1. 코딩 및 주석 스타일
사실 이런 건 개인적인 취향이나 기호가 반영되는 부분이라 프로그래머 대 프로그래머로서 남에게 간섭한다는 건 다소 무례한 일입니다만, 조금 실례하겠습니다.

(1) 주석

//파일포인터 선언
FILE *fp;
 
//스텍 생성
Stack *MainStack;
 
//파일의 총 문자열이 얼마나 되는지 알아내기위해 count 변수 사용및, 반복문을위한 i 선언.
int i,count;

이런 종류의 주석은 읽는 사람에게 도움이 되지 않습니다. 코드를 읽는 흐름을 깨트리기만 할 뿐이죠.
코드 한 라인이 하는 일을 그저 재서술하기만 할 뿐이거나 지나치게 자명한 주석은 지양하는 편이 좋습니다.

(2) 스택 동적 할당?
스택의 각 노드(Node)가 동적할당 되는 것은 이해할 수 있습니다. 그런데 MainStack은 왜 동적할당하시나요?
MainStack은 포인터로 선언해서 동적할당하는 것보다는 main의 지역변수로 직접 만드는 편이 더 좋을 것 같은데요.

역시 스타일의 문제입니다만, C언어에서 동적 할당은 불가피한 경우가 아니면 역시 지양하는 편이 좋다고 생각합니다.

2. 라이브러리 활용

중위 표현식을 읽기 위해 그 길이를 먼저 구하는 부분은 감탄스럽네요. 보통은 귀찮아서 char Input[1024] 같은 걸로 때우고 말죠. 그런 귀찮음이 버그를 만드는 건데 말입니다.
C언어에서 임의 길이 문자열을 입력받아서 처리하는 방법은 꽤 귀찮고, 이미 여러 방법이 알려져 있습니다만, 어쨌거나 피할 수 있으면 피하는 게 좋습니다.

그리고 바로 질문자님의 코드가 그걸 피할 수 있는 대표적인 예입니다. 메인 알고리즘에서 Input을 앞에서부터 한 글자씩, 되감지 않고 순서대로 읽고 있잖아요.
이러면 굳이 Input 배열에 모두 읽어들인 뒤 실행할 필요가 없죠. 필요할 때마다 fgetc 같은 함수로 읽어서 처리하면 되니까요.

귀찮은 버퍼링 같은 건 C library에 모두 맡겨 버립시다.

3. 로직 문제

2+3+4를 입력했더니 234를 출력하네요. 의도하신 거 아니죠?
질문자님이 제시하신 "달라지는 경우"를 살펴보니 덧셈의 왼쪽 결합(left associativity)이 무시되는 경우인 것 같아서, 덧셈/뺄셈이 연달아 등장했을 때 처리를 잘 못하는 것이 아닌가, 싶어서 간단히 확인해보니 바로 걸려드네요.

해결책까지 제시해 드릴 수 있으면 더 좋겠습니다만, 다른 사람이 짠 파서를 읽고 이해하여 최소한의 변경으로 고치는 건 조금 버거운 일입니다. 저도 한 번 시도해볼 테니, 질문자님도 생각을 좀 더 해 보시길 바랍니다.

Sift의 이미지

적어주신 세가지 팁들 잘 활용하겠습니다!
말씀해주신대로 로직에도 문제가 있었고 주석이 조금 난잡한것 같습니다.
라이브러리 활용또한 해보도록 하겠습니다!.
좋은 정보들 감사드립니다. 열심히 좋은코딩해보도록 하겠습니다.

tyhan의 이미지

http://www.tipssoft.com/bulletin/board.php?bo_table=FAQ&wr_id=714

연산자 우선순위와 연산 방향이 있습니다.
모범 답안과 연산 방향이 달라서 결과가 다른 것으로 예상됩니다.

덧셈에서는 문제가 없겠지만
곱셈과 나눗셈이 같은 연산자 우선순위라면

3/3*2 의 결과가 달라질 것으로 예상됩니다.
(3/3)*2, 3/(3*2) 이렇게 두가지로 해석 될 수 있기 때문입니다.

그럼 같은 연산자 우선순위에서의 연산 방향까지 고려하여 수정하면 될것입니다.

Sift의 이미지

말씀해주신대로 data.txt값에 넣어보니 제 로직이 틀렸다는것이 확실해졌습니다.
여러 테스트를 많이 해봤어야 했는데.. 답글 갑사합니다. 잘 고쳐보도록 하겠습니다!

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.