접미사 표현 식 을 접미사 표현 식 으로 변환 하고 값 을 구 합 니 다 (스 택 사용)

접두사 표현 식 은 2 * 3 + (4 - 3) 와 같 습 니 다. 연산 자 는 보통 연산 자 사이 에 나타 나 기 때문에 접두사 표현 식 이 라 고 합 니 다. 즉, 여러분 이 프로 그래 밍 에서 쓴 표현 입 니 다.
양식컴 파일 시스템 은 표현 식 의 우선 순 위 를 고려 하지 않 고 표현 식 을 왼쪽 에서 오른쪽으로 스 캔 할 뿐 연산 자 를 만 났 을 때 앞의 두 개 를 스 캔 합 니 다.
개 조작 수 를 꺼 내 조작 하 다.상기 목적 을 달성 하기 위해 서 는 접미사 표현 식 을 바 꾸 고 위의 표현 식 과 같은 접미사 표현 식 으로 바 꿔 야 합 니 다.
2 * 3 + (4 - 3) 는 23 * 4 3 - + 로 변 합 니 다.
접미사 표현 식 에는 괄호 가 포함 되 어 있 지 않 으 며 접미사 표현 식 의 조작 수 와 접미사 표현 식 의 조작 수 배열 순서 가 완전히 같 습 니 다. 연산 자 일 뿐 입 니 다.
순서 가 바 뀌 었 다.우리 가 실현 할 때 특정한 작업 방식 의 데이터 구조 (스 택) 만 사용 하면 실현 할 수 있다.
그 중 stack op;연산 자 창 고 를 보관 하 는 데 쓰 인 다.배열 ans 는 접미사 표현 식 을 저장 하 는 데 사 용 됩 니 다.
알고리즘 사상:
왼쪽 에서 오른쪽으로 접두사 표현 식 을 스 캔 합 니 다. 조작 수 는 배열 ans 의 끝 에 넣 습 니 다.
연산 자 라면 다음 세 가지 상황 으로 나 뉜 다.
1) '(' 이면 바로 op 창고 에 넣는다.
2) ')' 이 라면 op 스 택 에서 연산 자 를 꺼 내 배열 ans 의 끝 에 순서대로 추가 하여 '(') '를 만 나 는 것 을 알 수 있 습 니 다.
3) 괄호 가 아 닌 경우, 스 캔 한 연산 자 와 op 스 택 꼭대기 의 연산 자 를 비교 합 니 다. 스 캔 한 연산 자 우선 순위 가 스 택 꼭대기 연산 자 보다 높 으 면.
스 택 에 연산 자 를 눌 러 넣 습 니 다. 그렇지 않 으 면 스 택 에 있 는 연산 자 팝 업 을 배열 ans 의 끝 에 순서대로 추가 합 니 다. 우선 순위 가 스 캔 보다 낮 을 때 까지.
도착 한 연산 자 나 스 택 이 비어 있 고 스 캔 한 연산 자 를 스 택 에 눌 러 넣 습 니 다.
이렇게 차례대로 스 캔 해서 끝 날 때 까지 알 아 요.
스 캔 이 끝나 면 스 택 에 요소 가 있 으 면 배열 ans 의 끝 에 순서대로 팝 업 하면 접미사 표현 식 을 얻 을 수 있 습 니 다.
다음은 프로그램 코드 와 문제 설명 입 니 다.
질문 설명: 접미사 표현 식 을 접미사 표현 식 으로 변환 하 는 프로그램 을 만 드 십시오. 한 줄 만 입력 하면 접미사 표현 식 입 니 다. 입력 한 기호 에는 이 기본 기호 인 "0123456789 + - * / ()" 만 있 을 뿐 2 * - 3 과 같은 형식 은 나타 나 지 않 습 니 다. 모든 숫자 는 한 자릿수 입 니 다. "/"정수 연산 을 표시 합 니 다. 출력 은 한 줄 에 불과 합 니 다. 변 환 된 접미사 표현 식 입 니 다. 숫자 사이, 연산 자 사이, 숫자 와 연산 자 사 이 를 모두 빈 칸 으로 구분 합 니 다 (샘플 참조). 샘플. in 8 - (3 + 2 * 6) / 5 + 4. out 83 2 6 * + 5 / - 4 +
다음은 모든 코드 를 첨부 합 니 다.
/*
 * =====================================================================================
 *
 *       Filename:  math.c
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  2013 09 12  22 45 49 
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  gaoyuan, 
 *        Company:  Class 1204 of Computer Science and Technology
 *
 * =====================================================================================
 */

#include 
#include 
#include 
#include 
#include 

#define MAXSIZE 100

typedef struct number
{
	int num[MAXSIZE];
	int len;
}Number;

typedef struct operate
{
	char operate[MAXSIZE];
	int len;
}Operate;

int empty_num(Number *s)
{
	if (s->len == -1)
	{
		return 1;
	}

	return 0;
}

int push_num(Number *s, int x)
{
	if (s->len == MAXSIZE - 1)
	{
		return 0;
	}
	else
	{
		s->len++;
		s->num[s->len] = x;
		return 1;
	}
}

int pop_num(Number *s, int * data)
{
	if (empty_num(s) == 1)
	{
		return 0;
	}
	else 
	{
		*data = s->num[s->len];
		s->len--;
		return 1;
	}
}

int top_number(Number *s, int *data)
{
	if (empty_num(s) == 1)
	{
		return 0;
	}

	else 
	{
		*data = s->num[s->len];
		return 1;
	}
}
Number * init_number()
{
	Number *m;

	m = malloc(sizeof(Number));
	m->len = -1;

	return m;
}

int empty_operate(Operate *s)
{
	if (s->len == -1)
	{
		return 1;
	}

	return 0;
}

int push_operate(Operate *s, char oper)
{
	if (s->len == MAXSIZE - 1)
	{
		return 0;
	}

	else
	{
		s->len++;
		s->operate[s->len] = oper;
		return 1;
	}
}

int pop_operate(Operate *s, char *oper)
{
	if (empty_operate(s) == 1)
	{
		return 0;
	}

	else 
	{
		*oper = s->operate[s->len];
		s->len--;
		return 1;
	}
}

char top_operate(Operate *s)
{
	if (s->len == -1)
	{
		return 'n';
	}

	else
	{
		return s->operate[s->len];
	}
}

Operate * init_operate()
{
	Operate *m;

	m = malloc(sizeof(Operate));
	m->len = -1;

	return m;
}

int if_operte(char c)
{
	if (c == '*' || c == '+' || c == '-' || c == '/' || c == '(' || c == ')')
	{
		return 1;
	}

	return 0;
}

int level(char a)
{
	if (a == '+' || a == '-')
	{
		return 1;
	}

	else if (a == '*' || a == '/')
	{
		return 2;
	}

	else if (a == '(' || a == ')')
	{
		return 3;
	}

	else if (a == '=')
	{
		return 0;
	}
}

int judge_level(char a, char b)
{
		return (level(a) - level(b));
}
void translate(char * quest, char * ans ,int n)
{
	Operate *tmp;
	char c;

	tmp = init_operate();
	push_operate(tmp, '=');

	while (n--)
	{
//		printf("%c
", *quest); if ((*quest) >= '0' && (*quest) <= '9') { *ans++ = *quest; } else if ((*quest) == '(') // (, { push_operate(tmp, (*quest)); // printf("ya %c
", top_operate(tmp)); } else if ((*quest) == ')') // ), , ( { while (top_operate(tmp) != '(') { pop_operate(tmp, &c); *ans++ = c; // printf("c = %c
", c); *ans++ = ' '; // printf("ding %c %d
", top_operate(tmp), tmp->len); // getchar(); } pop_operate(tmp, &c); } else if (if_operte(*quest) == 1) { if (top_operate(tmp) == '(') { push_operate(tmp, *quest); } else if (judge_level(*quest, top_operate(tmp)) > 0) // , { push_operate(tmp, *quest); } else if (judge_level(*quest, top_operate(tmp)) <= 0) // , , { while (judge_level((*quest), top_operate(tmp)) <= 0 && (top_operate(tmp) != '=')) { pop_operate(tmp, &c); // printf("tan %c
", c); *ans++ = c; *ans++ = ' '; // *ans++ = *quest; } push_operate(tmp, *quest); // printf(" %c
", top_operate(tmp)); } } if (( if_operte(*quest) == 0) && (if_operte(*(quest + 1)) == 1)) { *ans++ = ' '; } quest++; } // printf(" %d
", tmp->len); while (tmp->len != 0) { pop_operate(tmp, &c); *ans++ = c; *ans++ = ' '; } *ans = '\0'; } int calculate (int num1, int num2, char ope) { int result; switch (ope) { case '*': result = num1 * num2; break; case '/': result = num1 / num2; break; case '+': result = num1 + num2; break; case '-': result = num1 - num2; break; } return result; } void result (char * string, int n) { char exp; char *p; int num, num3; int num1, num2; int i = 0, j = 0; int flag = 0; int tmp[MAXSIZE]; char ope[MAXSIZE]; Operate *operate; Number *number; operate = init_operate(); number = init_number(); p = string; while (*p != '\0') { num = 0; flag = 0; while ((*p) >= '0' && (*p) <= '9') { flag = 1; num = (*p - '0') + num * 10; p++; } if (flag == 1) { tmp[i++] = num; push_num(number, num); // printf(" %d %d
", num, number->len); } if (if_operte(*p) == 1) { pop_num(number, &num1); pop_num(number, &num2); // printf(" %d %d
", num1, num2); // printf(" %d
", number->len); push_num(number, calculate(num2, num1, *p)); top_number(number, &num3); /// printf("%d %c %d = %d
", num2, *p, num1, num3); // printf(" %d
", calculate(num2, num1, *p)); } p++; } top_number(number, &num); printf(" %d
", num); } int main(int argc, char *argv[]) { char string1[100]; char string2[100]; char *p, *q; printf("
"); scanf("%s", string1); // printf("%s
", string1); string1[strlen(string1)] = '\0'; // printf("
"); p = string1; q = string2; translate(p, q, strlen(string1)); printf("
%s
", string2); string2[strlen(string2)] = '\0'; result(string2, strlen(string2)); return EXIT_SUCCESS; }

좋은 웹페이지 즐겨찾기