접미사 식 계산기
5279 단어 데이터 구조
예컨대 접미사 식 - > (1 + 2) * 3 - 4 접미사 식 으로 변환 12+3*4-
접미사 식 에 대한 계산 은 매우 쉽다. 스 택 을 설정 하고 접미사 표현 식 을 왼쪽 에서 오른쪽으로 한 번 스 택 에 들 어 갑 니 다. 현재 스 택 에 들 어 가 는 것 이 숫자 라면 스 택 에 넣 습 니 다.
연산 자 라면 스 택 에서 두 개의 숫자 를 꺼 내 해당 하 는 연산 을 한 다음 에 연산 후의 숫자 를 스 택 으로 되 돌려 줍 니 다.문자열 이 완전히 처 리 된 후에 스 택 지붕 은 연산 결과 입 니 다.
PS: 입력 한 접미사 표현 식 은 합 법 적 이 어야 합 니 다.
그러면 접미사 표현 식 은 어떻게 접미사 표현 식 으로 바 꿉 니까?(ch 는 접두사 표현 식 이 전달 하 는 문 자 를 받 아들 입 니 다)
1: ch 는 '(' 창고 에 넣 기;
2: ch 는 ')' 스 택 에 입력 한 연산 자 입 니 다. '(' 를 만 날 때 까지.
3: ch 가 다른 합 법 적 인 문자 라면 ch 를 현재 스 택 지붕 과 비교 합 니 다.
a: ch 우선 순위 가 스 택 꼭대기 요소 보다 높 고 ch 가 스 택 에 들 어 갑 니 다.
b: ch 우선 순위 가 스 택 꼭대기 요소 보다 낮 거나 같 습 니 다. 스 택 꼭대기 요 소 를 출력 하고 ch 가 스 택 에 들 어 갑 니 다.
4: 접미사 표현 식 읽 기 가 완료 되면 스 택 에 있 는 요 소 를 스 택 이 비 어 있 을 때 까지 순서대로 출력 합 니 다.
예 를 들 어:
접두사 표현 식 (A - B) / C + D
1: '(' 창고 에 들 어가 기 '
2: A - > 출력 문자 누 르 기
3: - 입고
4: B 출력 문자열 누 르 기
5: ')' 출력 스 택 에 있 는 문자 부터 출력 문자열 까지
6: '/' 입고
7: C 압축 문자열
8: ’+‘ ’/‘창고 에서 나 와 서 '+' 창고 에 들 어가 세 요.
9: D 출력 문자열 압축
10: 스 택 에 남 은 문자열 을 순서대로 출력 합 니 다.
#include
#include
#include
#define MAX_STACK_SIZE 100
#define MAX_EXPR_SIZE 100
void postfix(char *expr,char *outstr);
int eval(char *outstr);
typedef enum {lparen,rparen,pluss,minuss,timess,divide,mod,eos,operand} precedence;
int stack_int[MAX_STACK_SIZE];
precedence stack_prece[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE];
int isp[] = {1,19,12,12,13,13,13,0};
int icp[] = {20,19,12,12,13,13,13,0};
#define INT_ITEM 1
#define PRECE_ITEM 2
//
void push(int *top,int a,precedence b,int flag)
{
if(*top >= MAX_STACK_SIZE - 1)
{
printf("stack overflow.
");
exit(1);
}
//
if(flag==INT_ITEM)
stack_int[++*top] = a;
else if(flag == PRECE_ITEM)
stack_prece[++ *top] = b;
}
//
void pop(int *top,int *a,precedence *b,int flag)
{
if(*top < 0)
{
printf("stack overflow.
");exit(1);
}
// a b
if(flag == INT_ITEM)
*a = stack_int [(*top)--];
else if(flag == PRECE_ITEM)
*b = stack_prece[(*top)--];
}
//
precedence get_token(char *symbol,int *n,char *expr)
{
*symbol = expr[(*n)++]; // n
switch(*symbol){
case '(': return lparen;
case ')': return rparen;
case '+': return pluss;
case '-': return minuss;
case '*': return timess;
case '/': return divide;
case '%': return mod;
case '\0': return eos;
default: return operand; //
}
}
//
char precedencetochar(precedence token)
{
switch(token){
case pluss: return '+';
case minuss: return '-';
case divide: return '/';
case timess: return '*';
case mod: return '%';
case eos: return '\0'; //
default : return operand; //
}
}
//
void postfix(char *expr,char *outstr)
{
char symbol;
precedence token,precevalue;
int n=0;
int intvalue;
int i=0;
int top = -1;
stack_prece[0] = eos;
for(token = get_token(&symbol,&n,expr);token!=eos;token = get_token(&symbol,&n,expr))
{
//
if(token == operand)
outstr[i++] = symbol;
//
else if(token == rparen){
while(stack_prece[top] != lparen)
{
pop(&top,&intvalue,&precevalue,PRECE_ITEM);
outstr[i++] = precedencetochar(precevalue);
}
pop(&top,&intvalue,&precevalue,PRECE_ITEM);
}
// ,
else
{
if(top >=0)
while(isp[stack_prece[top]] >= icp[token])
{
pop(&top,&intvalue,&precevalue,PRECE_ITEM);
outstr[i++] = precedencetochar(precevalue);
}
push(&top,0,token,PRECE_ITEM);
}
}
while(top >= 0)
{
pop(&top,&intvalue,&precevalue,PRECE_ITEM);
outstr[i++] = precedencetochar(precevalue);
}
outstr[i] = '\0';
}
//
int eval(char *outstr)
{
precedence token,precevalue;
char symbol;
int op1,op2,result;
int n=0;
int top = -1;
token = get_token(&symbol,&n,outstr);
precevalue = token;
while(token != eos)
{
if(token == operand)
push(&top,symbol-'0',precevalue,INT_ITEM);
else
{
pop(&top,&op2,&precevalue,INT_ITEM);
pop(&top,&op1,&precevalue,INT_ITEM);
switch(token){
case pluss : push(&top,op1+op2,precevalue,INT_ITEM);break;
case minuss : push(&top,op1-op2,precevalue,INT_ITEM);break;
case timess : push(&top,op1*op2,precevalue,INT_ITEM);break;
case divide : push(&top,op1/op2,precevalue,INT_ITEM);break;
case mod : push(&top,op1%op2,precevalue,INT_ITEM);break;
default : break;
}
}
token = get_token(&symbol,&n,outstr);
}
pop(&top,&result,&precevalue,INT_ITEM);
return result;
}
int main()
{
char expr[100],outstr[100];
int result;
gets(expr); //
postfix(expr,outstr);
result = eval(outstr);
printf("the result is %d
",result);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.