중위연산식을 후위연산식으로 바꿔서 출력하기
글쓴이: kimscom / 작성시간: 화, 2008/05/27 - 2:24오전
책의 소스인데요. 숫자가 아닌 (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();
} Forums:


C로 배우는 알고리즘 - 이재규
자세하게 그림설명으로 나와 있습니다.
원리는 간단합니다. 스택만 이해하신다면..
그리고, 이산수학을 선이수하시면 도움이 조금 될겁니다.
Hello World.
마침 전에 과제로
마침 전에 과제로 했던 파일이 남아있어 올립니다
gcc 에서 한 겁니다
글을 보니 숫자가 아닌 문자로 받겠다고 하셨는데
그러면 isdigit()만 수정해서 쓰시면 될것 같습니다
/* infix_to_postfix.c */ #include <ctype.h> #include <stdio.h> /* to use printf() */ #include <stdlib.h> /* 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.
댓글 달기