중위연산식을 후위연산식으로 바꿔서 출력하기

kimscom의 이미지

책의 소스인데요. 숫자가 아닌 (a+b)*c 이런식으로 문자로 입력해서 결과를 후위연산으로 출력되게 하고 싶습니다.
아직 뭐가 뭔지 잘 몰라 그러니 완성된 소스를 좀 알려주시면 보고 공부하는데 많이 도움이 될 것 같네요.. 부탁드립니다.
계산 자체는 필요없구요.. 그냥 후위연산처리된 결과만 보이면 됩니다.

#include [stdio.h] // 꺽쇠가 자꾸 사라져서 []로 했습니다.
#include [stdlib.h] 
#include [string.h] 
 
typedef int element;
 
typedef struct stackNode {			
	element data; 
	struct stackNode *link; 
}stackNode; 
 
stackNode* top;
 
void push(element item) 
{	
	stackNode* temp=(stackNode *)malloc(sizeof(stackNode));
	temp->data = item; 
	temp->link = top;	
	top = temp; 
} 
 
element pop() 
{ 
	element item;
	stackNode* temp=top;
 
	if(top == NULL) { 	 
		printf("\n\n Stack is empty !\n");	 
		return 0; 
	} 
	else { 
		item = temp->data;	
		top = temp->link;	 
		free(temp);				
		return item; 
	} 
} 
 
element peek() 
{	
	element item; 
	if(top == NULL) {		 
		printf("\n\n Stack is empty !\n");	 
		return 0;	 
	} 
	else { 
		item = top->data; 
		return item; 
	} 
} 
 
void del() 
{  
	stackNode* temp; 
	if(top == NULL) {		
		printf("\n\n Stack is empty !\n");	
 
	} 
	else { 
		temp = top;	
		top = top->link;	 
		free(temp); 
	} 
} 
 
void printStack()
{
	stackNode* p=top;
	printf("\n STACK [ ");
	while(p){
		printf("%d ",p->data);
		p = p->link;
	}
	printf("] ");
}
 
element evalPostfix(char *exp)
{
	int opr1, opr2, value, i=0;
	int length = strlen(exp);
	char symbol;
	top = NULL;
 
	for(i=0; i<length; i++){
		symbol = exp[i];
		if(symbol != '+' && symbol != '-' && symbol != '*' && symbol != '/'){
			value = symbol - '0';
			push(value);
		}
		else{
			opr2 = pop();
			opr1 = pop();
			switch(symbol){
			case '+' : push(opr1 + opr2); break;
			case '-' : push(opr1 - opr2); break;
			case '*' : push(opr1 * opr2); break;
			case '/' : push(opr1 / opr2); break;
			}
		}
	}
	return pop();
}
 
void main(void) 
{ 		
	int result;
	char* express = "35*62/-";
	printf("후위표기식 : %s", express);
 
	result = evalPostfix(express);
	printf("\n\n 연산결과 => %d", result);
 
	getchar();
} 
오호라의 이미지

자세하게 그림설명으로 나와 있습니다.

원리는 간단합니다. 스택만 이해하신다면..

그리고, 이산수학을 선이수하시면 도움이 조금 될겁니다.

Hello World.

bluelenz의 이미지

마침 전에 과제로 했던 파일이 남아있어 올립니다
gcc 에서 한 겁니다
글을 보니 숫자가 아닌 문자로 받겠다고 하셨는데
그러면 isdigit()만 수정해서 쓰시면 될것 같습니다

/* infix_to_postfix.c */
 
#include &lt;ctype.h&gt;
#include &lt;stdio.h&gt;		/* to use printf()	*/
#include &lt;stdlib.h&gt;	/* to use exit()	*/
 
int lookahead;
 
main()
{
	lookahead = getchar();
	expr();
	putchar('\n');
}
 
/*
 
*/
expr()
{
	term();			/* 첫번째 character는 숫자이므로 출력한다 -error는 term()에서 check	*/
 
	while(1){
		if(lookahead == '+'){		/* lookahead가 연산기호이면 match()를 호출하여	*/
			match('+');		/* 다음 character를 lookahead에 assign하고	*/
			term();			/* term()을 호출하여 숫자를 출력한 후 기호를 출력한다	*/
			putchar('+');
		}
		else if(lookahead == '-'){
			match('-');
			term();
			putchar('-');
		}
		else if(lookahead == ')' || lookahead == '\n')
			break;		/* ')' : factor()에서 expr()를 호출했을 때 return을 위해	*/
		else			/* '\n' : 끝날 때	*/
			error();
	}
}
 
/*
lookahead가 숫자이면 출력 후 match() 호출
*/
term()
{
	while(isdigit(lookahead)){	/* 여러자리의 숫자를 처리하기 위해			*/
		putchar(lookahead);	/* lookahead가 숫자일 동안 while loop		*/
		match(lookahead);
	}
	if(lookahead == '('){		/* term 에서 '('가 나오면 factor() 호출		*/
		factor();
		match(lookahead);
	}
}
 
/*
term 에서 '('가 나오면 호출
')'가 나올 때 까지 expr()재귀호출
*/
factor()
{
	match(lookahead);
	while(lookahead != ')'){	/* factor : ( expr )*/
		expr();
	}
}
 
/*
다음 character를 읽어 lookahead에 assign
공백문자이면 다시 읽어온다
*/
match(t)
	int t;
{
	do{
		lookahead = getchar();
	}while(lookahead == ' ' || lookahead == '\t');
}
 
/*
error 메시지 출력 후 프로그램 종료
*/
error()
{
	printf("syntax error\n");
	exit(1);
}

소스를 해석해달라는 말씀이셨군요;;;

오호라의 이미지

'*', '/' 가 없네요. ^^;

과제를 그대로 제출하셨다면 낭패를 봤을듯한데요. ^^;

보통 자료구조 수업의 과제로 나오죠. 큐와 스택을 이용해서 하죠.

위와 같은 소스는 컴파일러책(드래곤북)에서 단순한 패스컴파일러(드래곤북, 컴파일러의 프론트엔드쪽 스캐너(형태소분석기) & 파서 & 코드생성기 합친 단순모형)에서 나오죠.

과제도 수업, 강사, 교수의 레벨(수준, 어감이 좀 그렇군요. ^^; )에 따라 제출해야 하죠.

저도 OOP 수업에서 이 과제발표할때 위의 얘기했다고 된통 면박(?)을 당했죠. ㅋㅋㅋ

ps. 차라리 lex & yacc 이용함을 추천. 교수도 훌륭(?)하다고 생각해줌(?)... ^^;

Hello World.

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.