Notation.exe이것은 C로 작성된 Infix to postfix 변환 프로그램
Infix_to_Postfix.c/************************************************************************
* infix_to_postfix.c
* 중위표기식을입력받아후위표현식으로변환하고
* 계산하여그결과를보여주는프로그램
*************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FALSE 0
#define TRUE 1
#define MAX_STACK_SIZE 100 // 최대스택사이즈
#define MAX_EXPR_SIZE 100 // 수식최대사이즈
typedef enum {
LPAREN
, RPAREN , PLUS,
MINUS , TIMES,
DIVIDE , MOD ,
LOGICAL_AND
, LOGICAL_OR ,LEFT_SHIFT
, RIGHT_SHIFT ,
EQUAL ,
NOT_EQAUL ,
LESS , GRATER
, LESS_EQUAL
, GRATER_EQUAL ,
EOS , OPERAND
} PRECEDENCE; // 우선순위
//////////////////////////////////////////////////////////////////////////
// Global Variable.
int stack[MAX_STACK_SIZE]; // 수식에대한스택
char expr[MAX_EXPR_SIZE]; // 수식을저장하는문자배열.
//
in-stack precedence
const int isp[]
= {
0,19,12,12,13,13,13,5,4,11,11,9,9,10,10,10,10,0 };
//
incoming precedence
const int icp[]
= { 20,19,12,12,13,13,13,5,4,11,11,9,9,10,10,10,10,0 };
/************************************************************************
* Function Prototype
Declaration.
*************************************************************************/
int eval( void ); // 후위표현수식을계산.
void stack_push( int* top , int item ); // 스택푸쉬.
int stack_pop( int* top ); // 스택팝
void postfix( void ); // 수식을후위표현으로변환
// 후위표현으로표현된수식중연산자를문자로표현
void print_token( PRECEDENCE
token , char**
str );
// 토큰을받아옴. 토큰의종류
PRECEDENCE get_token( char* symbol , int* n );
//////////////////////////////////////////////////////////////////////////
// main 함수
int main ( void )
{
printf("----------------------------------\n");
printf("| Converting
infix to postfix |\n");
printf("----------------------------------\n\n");
printf("수식을입력하세요( ex : \"3*9/2+3(ENTER)\" )\nInput : ");
scanf("%s" , expr); // 수식입력받음
postfix(); //
후위표기로변환
printf("\n\n결과: %d \n\n", eval() ); // 후위식을계산.
return
0;
}
//////////////////////////////////////////////////////////////////////////
// 해당식을후위연산자로변환
void postfix ( void )
{
char symbol; // 연산자, 피연산자
char expr_post[MAX_EXPR_SIZE]
= {0,}; // 후위표기식으로저장하는문자열.
char* str = expr_post; // 어디까지읽었는지저장하기위한포인터.
PRECEDENCE
token; // 토큰을받는변수
int n = 0 , top = 0; // 문자열의인덱스, 스택탑
// 스택의제일처음은EOS
stack[0]
= EOS;
// 중위-> 후위변환알고리즘책참조.
// 토큰이EOS, 즉문자의끝일때까지반복
for ( token = get_token(
&symbol , &n
) ; token != EOS
;
token
= get_token( &symbol
, &n ) )
{
if
( token == OPERAND
) // 피연산자라면출력.
*str++
= symbol;
else
if (token == RPAREN )
{ // 폐괄호라면.
while(
stack[top] !=
LPAREN ) // 스택탑이개괄호전까지
print_token(stack_pop(&top) , &str ); // 스택의내용을차례대로출력.
stack_pop(&top); // 스택의탑, 즉개괄호는버린다.
}
else
{
//
폐괄호가아니라면
//
연산자우선순위를검사.
//
들어오는쪽이스택안의것보다우선순위가높거나같을때까지.
while
( isp[stack[top]] >= icp[token] )
print_token(stack_pop(&top) , &str ); // 스택내용을출력.
stack_push(
&top , token
); // 들어갈려하는토큰삽입.
}
}
// 나머지스택내의내용들을문자열에저장.
while (
(token = stack_pop(&top)) != EOS
&& top > -1)
print_token(token , &str );
// 후위표현출력.
printf("postfix expression : %s \n" , expr_post );
strcpy(
expr , expr_post
); // 전역변수에저장.(계산)
}
//////////////////////////////////////////////////////////////////////////
// 토큰의종류를반환.
PRECEDENCE get_token( char* symbol , int* n )
{
switch(
*symbol = expr[(*n)++] )
{
case '(': return LPAREN;
case ')': return RPAREN;
case '+': return PLUS;
case '-': return MINUS;
case '/': return DIVIDE;
case '*': return TIMES;
case '%': return MOD;
case '\0': return EOS;
case '<':
if
( expr[*n] =='<' ){ // < 뒤에문자가<일경우
//
포인터를다음문자를가르키고left shift 연산자반환
++*(n); return LEFT_SHIFT;
}
else
if ( expr[*n] == '=' ) { // = 라면
++*(n); return LESS_EQUAL; // less or equal 연산자반환
}
return
LESS; // 그렇지않다면less then 반환.
case '>':
if ( expr[*n] == '>' ){ // > 뒤에문자가>일경우
++*(n); return RIGHT_SHIFT; // right shift 연산자반환
}
else
if ( expr[*n] == '=' ){ // = 라면
++*(n); return GRATER_EQUAL;
// grater or
equal 연산자반환
}
return
GRATER; // 그렇지않다면grater then 반환
case '&':
if
( expr[*n] ==
'&' ){ // & 뒤에문자가&일경우
++*(n); return LOGICAL_AND; // logical and 연산자반환
}
return
EOS;
case '|':
if
( expr[*n] =='|' ){ // | 뒤에문자가| S일경우
++*(n); return LOGICAL_OR; // logical or 연산자반환
}
return
EOS;
case '=':
if(
expr[*n] == '=') { // = 뒤에문자가= 일경우
++*(n); return EQUAL; // logical equal 연산자반환
}
return
EOS;
case '!': // ! 뒤에문자가= 일경우
if
( expr[*n] =='=' ){
++*(n); return NOT_EQAUL; // logical not equal
연산자반환
}
return
EOS; // 그렇지않다면eos 반환
default
: return OPERAND; //
기본값으로피연산자반환
}
}
//////////////////////////////////////////////////////////////////////////
// 후위표기식을 계산.
int eval(void)
{
PRECEDENCE
token; // 토큰
char symbol; // 문자
int op1,
op2; // 피연산자1 ,2
int n =
0; // 문자열의인덱스
int top
= -1; // 스택탑
// 토큰을받아옴
token =
get_token( &symbol
, & n );
while ( token != EOS )
{
// 피연산자라면문자를숫자로변환해서스택에넣는다.
if(
token == OPERAND
)
stack_push(
&top , symbol
- '0' );/*문자로된값을숫자로변환*/
else{
//
symbol이연산자라면
//
스택에저장해놨던피연산자를꺼내온다.
//
예를들어a b c +
d * - 에서‘+’연산을하는피연산자는
// 스택탑과바로밑의피연산자이다.
//
스택에는밑에서부터a
, b , c 상으로저장되어있는데.
//
c + b 가아니라b + c 이기때문에역순으로받아와야한다.
op2
= stack_pop(&top); // 두번째피연산자.
op1
= stack_pop(&top); // 첫번째피연산자.
switch(
token )
{ // 해당연산자에맞게연산하여그결과값을스택에저장.
case
PLUS: stack_push( &top
, op1 + op2
); break;
case
MINUS: stack_push( &top
, op1 - op2
); break;
case
TIMES: stack_push( &top
, op1 * op2
); break;
case
DIVIDE: stack_push( &top
, op1 / op2
); break;
case
MOD: stack_push( &top
, op1 % op2
); break;
case LOGICAL_AND: stack_push(
&top , op1
&& op2 ); break;
case
LOGICAL_OR : stack_push( &top
, op1 || op2
); break;
case
LEFT_SHIFT: stack_push( &top
, op1 << op2
); break;
case
RIGHT_SHIFT : stack_push( &top
, op1 >> op2
); break;
case
EQUAL : stack_push( &top
, op1 == op2
); break;
case
NOT_EQAUL : stack_push( &top
, op1 != op2
); break;
case
LESS : stack_push( &top
, op1 < op2
); break;
case
GRATER: stack_push( &top
, op1 > op2
); break;
case
LESS_EQUAL: stack_push( &top
, op1 <= op2
); break;
case
GRATER_EQUAL: stack_push( &top
, op1 >= op2
); break;
default: break;
}
}
// 연산후해당문자의토큰값을받아온다
token
= get_token( &symbol
, &n );
}
// 최종결과값을반환.
return stack_pop( &top
); // 결과반환
}
//////////////////////////////////////////////////////////////////////////
// 해당토큰에해당하는기호(연산자)로문자로삽입.
void print_token( PRECEDENCE token , char** str )
{
switch( token )
{
case PLUS: *(*str)++
= '+'; return; // +
case MINUS: *(*str)++
= '-'; return; // -
case DIVIDE: *(*str)++ = '/'; return; // /
case TIMES: *(*str)++
= '*'; return; // *
case MOD: *(*str)++ = '%'; return; // %
case LESS : *(*str)++ = '<'; return; // <
case GRATER: *(*str)++ = '>'; return; // >
//
& 문자다음에& 문자를하나더삽입, 밑의연산자가2개의공간를차지하는것도같게처리
case LOGICAL_AND: *(*str)++ = '&'; *(*str)++
= '&'; return;
case LOGICAL_OR : *(*str)++ = '|'; *(*str)++
= '|'; return; // ||
case LEFT_SHIFT: *(*str)++ = '<'; *(*str)++
= '<'; return; // <<
case RIGHT_SHIFT : *(*str)++ = '>'; *(*str)++
= '>'; return; // >>
case EQUAL : *(*str)++ = '='; *(*str)++
= '='; return; // ==
case NOT_EQAUL : *(*str)++ = '!'; *(*str)++
= '='; return; // !=
case LESS_EQUAL: *(*str)++ = '<'; *(*str)++
= '='; return; // <=
case GRATER_EQUAL: *(*str)++ = '>'; *(*str)++
= '='; return; // >=
case EOS: return;
default
: return;
}
}
//////////////////////////////////////////////////////////////////////////
// 스택푸쉬
void stack_push( int* top , int item )
{
if ( (*top) == MAX_STACK_SIZE
) fprintf(stderr
, "The stack is full.\n" ), exit(1);
stack[++(*top)] = item ;
}
//////////////////////////////////////////////////////////////////////////
// 스택팝
int stack_pop( int* top )
{
if ( (*top) == -1 ) return EOS;
return stack[(*top)--];
}
'# IT, Computer Science > Algorithm' 카테고리의 다른 글
| Master theorem (마스터 이론) (0) | 2012.10.30 |
|---|---|
| 셀프넘버 (Self Number) (0) | 2012.02.18 |
| Bloom filter(블룸 필터) (0) | 2009.12.16 |
| Binary search tree (0) | 2009.11.14 |
| Full Binary Tree and Complete Binary Tree (1) | 2009.10.07 |
