officialandrey
@officialandrey

Польская запись. В чем ошибка?

Дано выражение a*b/(a+b). Организовать вычисление этого выражения, используя алгоритм польской записи. Применить системный стек.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

int main ()
{
	P_STACK st;
	P_NODE nd;
	char expr = "*+ab-cd";
	char ch;
	int a, b, c, d, i, aStep, bStep, cStep, dStep, add, mult, sub, res;
	st = (P_NODE) malloc (sizeof (stack));
	init_stack (st);
	i = 0;
	while (expr[i]!='\0')
	{
		nd=(P_NODE) malloc (sizeof (node));
		nd->info=expr[i];
		push (st, nd);
		i++;
	}
	printf ("Enter the 4th number:");
	scanf ("%d%d%d%d", &a, &b, &c, &d);
	while (!is_stack_empty (st))
	{
		nd = pop (st);
		if (!is_stack_empty (st))
			switch (nd->info)
			{
				case 'd':
					dStep=d;
					break;
				case 'c':
					cStep=c;
					break;
				case '-':
					sub=cStep-dStep;
					break;
				case 'b':
					bStep=b;
					break;
				case 'a':
					aStep=a;
					break;
				case '+':
					add=bStep+aStep;
					break;
				case '*':
					mult=add*sub;
					break;
			}
	}
	res=mult;
	printf ("Result: [expr=%d] = [%d]", expr, res);
	return 0;
}

Вот библиотека:
#ifndef STACK_H_
#define STACK_H_

typedef struct NODE NODE;
typedef struct NODE *P_NODE;
typedef struct STACK STACK;
typedef struct STACK *P_STACK;

struct NODE
{
	int info;
	P_NODE next;
} node;

struct STACK
{
	int count;
	int size;
	P_NODE top;
} stack;

typedef enum {false, true} bool;
void init_stack (P_STACK st);
bool is_stack_empty (P_STACK st);
void push (P_STACK st, P_NODE nd);
P_NODE pop (P_STACK st);
void print_stack (P_STACK st);


#endif
  • Вопрос задан
  • 164 просмотра
Пригласить эксперта
Ответы на вопрос 1
@res2001
Developer, ex-admin
У вас в коде забито другое выражение: (a + b) * (c - d)
Где реализация стека?

По реализации:
1. Для вычислений вам не нужны 4 переменные или 10 (в зависимости от того сколько в выражении), достаточно двух для обычных бинарных операций (с двумя операндами). Результат промежуточного вычисления нужно снова вставлять в стек в место вытащенных операндов и операции.
2.Алгоритм вычисления по прямой польской нотации неплохо описан на вики.
нужно считывать выражение слева направо, рассматривая оператор и ближайшие к нему два операнда. Если среди этих операндов находится еще один оператор, то вычисление первого оператора откладывается, до тех пор, пока не будет вычислен новый оператор. Итерации этого процесса повторяются до тех пор, пока оператор не будет вычислен, что должно в конечном счете произойти, если в выражении количество операндов на один больше, чем количество операций (в случае бинарных операций). Как только оператор вычислен, он и его два операнда заменяются полученным значением (операндом). Поскольку оператор и два операнда заменяются на вычисленный операнд, то становится на один оператор и один операнд меньше.

Таким образом стек тут не очень подходит, кроме операций push и pop нужно еще делать и обход списка в прямом направлении и вставка/удаление элементов в произвольной позиции.
Либо как вариант со стеком - использовать 2 стека. Т.е из одного извлекаете отложенные и результаты вычислений помещаете во второй пока первый не опустеет, затем переключаетесь на второй и так до тех пор пока в стеке не останется единственное значение - результат вычислений.
Либо с одним стеком, но изменить реализацию. Так чтобы не было структуры P_STACK.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
19 апр. 2024, в 03:52
1000 руб./за проект
19 апр. 2024, в 03:01
1000 руб./за проект
18 апр. 2024, в 21:56
2000 руб./за проект