Дано выражение a*b/(a+b). Организовать вычисление этого выражения, используя алгоритм польской записи. При решении использовать стек.
Алгоритм:
1. Инициализируем стек.
2. Записываем выражение a*b/(a+b) в виде польской записи: ab*ab+/. Заносим его в массив.
3. Проходим каждый элемент массива, если встречаем число, то заносим его в стек, если знак операции -- достаем из стека два числа, выполняем над ними эту операцию и заносим результат в стек.
4. При окончании данных в массиве получаем результат из стека.
#include <stdio.h>
#define LEN 7
int Record[LEN];
/*
* Стек.
*/
struct Stack {
int data[LEN];
int size;
};
typedef struct Stack Stack;
void StackInit(Stack *S) { S->size = 0; }
int StackTop(Stack *S)
{
if (S->size == 0) {
fprintf(stderr, "Error: stack empty\n");
return -1;
}
return S->data[S->size-1];
}
void StackPush(Stack *S, int d)
{
if (S->size < LEN) S->data[S->size++] = d;
else fprintf(stderr, "Error: stack full\n");
}
void StackPop(Stack *S)
{
if (S->size == 0) fprintf(stderr, "Error: stack empty\n");
else S->size--;
}
/*
* Ф-ия вычисления выражения записанного в массив Record
*/
void compute (Stack *S)
{
extern Record[];
int i;
int a,b;
for (i=0; i<LEN; i++)
{
switch(Record[i])
{
case '+':
case '*':
case '-':
case '/':
a=StackTop(S); StackPop(S);
b=StackTop(S); StackPop(S);
if (Record[i] == '+') StackPush(S, b+a);
else if(Record[i] == '*') StackPush(S, b*a);
else if(Record[i] == '/') StackPush(S, b/a);
else if(Record[i] == '-') StackPush(S, b-a);
break;
default:
StackPush(S,Record[i]);
}
}
}
/*
* Main
*/
int main ()
{
extern Record[];
int a,b;
int res;
Stack S;
StackInit(&S);
printf("Expression: a*b/(a+b) -> ab*ab+/\n");
printf("Please, write values 'a' and 'b': ");
scanf("%d %d",&a,&b);
printf("\n");
if (a == 0 || b == 0)
res=0;
else {
Record[0]= a ; // a*b/(a+b) -> ab*ab+/
Record[1]= b ;
Record[2]='*';
Record[3]= a ;
Record[4]= b ;
Record[5]='+';
Record[6]='/';
compute(&S);
res=StackTop(&S); StackPop(&S);
}
printf("Result: %d\n\n", res);
return 0;
}
Ключевые слова:
польская запись, стек, динамический массив
