Из инфиксной нотации в постфиксную

[Elnamir]

Здравствуйте, прошу помощи, есть класс в нем методы. Суть программы в том что она должна переводить из инфиксной нотации в постфисную, но где то накосячил, понять не могу где

PHP код:

#include <iostream>
#include <string>
#include <ctype.h>
#define MAX_SIZE 256
using namespace std;

class calc
{
private:
    char* infixStroka;
    char stack[MAX_SIZE];
    char* PostfixStroka; // Выходная строка постфиксной нотации
    int size; //Размер строки
    int n; // Счетчик стека
public:
    calc(char str[])
    {
        n = 0;
        while(n <= 256)
            stack[n++] = ' ';
        n = 0;
        size = strlen(str);
        infixStroka = new char[size];
        PostfixStroka = new char[size];
        for(int i = 0; i <= size; i++)
            infixStroka[i] = str[i];
    }
    void push(char b)
    {
        stack[n++] = b;
    }
    char pop()
    {
        return stack[n--];
    }
    void InftoPost()
    {

        int j = 0;
        for(int i = 0; i <= size; i++)
        {
            
            if(isdigit(infixStroka[i]) || infixStroka[i] == 'x')
            {
                PostfixStroka[j] = infixStroka[i];
                j++;
            }
            else if(infixStroka[i] == '+' || infixStroka[i] == '-' || infixStroka[i] == '*' || infixStroka[i] == '/' || infixStroka[i] == '^')
                push(infixStroka[i]);
            else if(infixStroka[i] == '(')
                push(infixStroka[i]);
            else if(infixStroka[i] == ')')
            {
                char good = pop();
                do
                {
                    PostfixStroka[j] = good;
                    good = pop();
                    j++;
                }
                while(good != '(');
            }    


        }
        while(n != 0)
            PostfixStroka[j++] = pop();

    }
    void display()
    {
        cout << "infixStroka: " << infixStroka << endl;
        cout << "PostFixStroka: " << PostfixStroka << endl;
    }
};
int main()
{
    calc a("3+4+5");
    a.InftoPost();
    a.display();
    return 0;
} 


Помогите найти ошибку в логике алгоритма моей программы, большое спасибо.

[nikmoon]

Примерно воть.

#include <iostream>
#include <cstring>

using namespace std;


#define MAX_LEN 256


void push(char *_stack, int &_ptr, char data);
char pop(char *_stack, int &_ptr);

//
//	Преобразование записи математ. выражения из инфиксной в постфиксную (в обратную польскую запись)
//
//	Сразу оговоримся, допустимые операторы: +,-,*,/,(,),^; все операции будем считать лево-ассоциативными
//	Все операнды - односимвольные
//
void PostfixNotation(const char *_infix, char *_postfix)
{
	char stack[MAX_LEN];	// стек для хранения операторов при преобразовании
	int st_ptr = 0;				// указатель вершины стека

	int out_index = 0;		// индекс в выходной строке
	int in_index = 0;		// индекс во входной строке

	// начинаем разбор входящей строки (она не должна быть пустой)
	do
	{
		char c = _infix[in_index];	// берем текущий символ входной строки

		switch (c)
		{
			case '+':
			case '-':
				// выталкиваем из стека в выходную строку все операторы с большим или равным приоритетом
				while (st_ptr != 0)
				{
					char op = stack[st_ptr-1];	// оператор в вершине стека
					if (op != '(')	// все операторы, кроме откр. скобки имеют больший или равный приоритет
					{
						_postfix[out_index++] = op;	// добавляем оператор в выходную строку
						pop(stack, st_ptr);			// удаляем оператор из стека
					}
					else
						break;
				}
				// помещаем оператор в стек
				push(stack, st_ptr, c);
				break;

			case '*':
			case '/':
				// выталкиваем из стека в выходную строку все операторы с большим или равным приоритетом
				while (st_ptr != 0)
				{
					char op = stack[st_ptr-1];
					if ((op == '^') || (op == '*') || (op == '/'))
					{
						_postfix[out_index++] = op;	// добавляем оператор в выходную строку
						pop(stack, st_ptr);			// удаляем оператор из стека
					}
					else
						break;
				}
				// помещаем оператор в стек
				push(stack, st_ptr, c);
				break;

			case '(':
				// просто помещаем в стек
				push(stack, st_ptr, c);
				break;

			case ')':
				// выталкиваем из стека в выходную строку все элементы до открывающей скобки (откр. скобку просто отбрасываем)
				while (st_ptr != 0)
				{
					char op = pop(stack, st_ptr);	// забираем из стека оператор
					if (op == '(')					// если достигли открывающей скобки
						break;						// выталкивание закончили
					else
					{
						_postfix[out_index++] = op;	// добавили оператор в выходную строку
					}
				}
				break;

			case '^':
				// помещаем оператор в стек (выталкивать ничего не нужно, нет операторов с большим приоритетом)
				push(stack, st_ptr, c);
				break;

			default:		// символ цифры
				_postfix[out_index] = c;	// добавляем цифру в выходную строку
				out_index++;
				break;
		}

		in_index++;	// переходим к следующему символу входной строки
	}
	while (_infix[in_index] != 0);	// разбор закончен

	// выталкиваем все операторы в выходную строку
	while(st_ptr != 0)
		_postfix[out_index++] = pop(stack, st_ptr);

	// завершающий символ нуля
	_postfix[out_index] = 0;
}


void push(char *_stack, int &_ptr, char data)
{
	_stack[_ptr++] = data;
}

char pop(char *_stack, int &_ptr)
{
	return _stack[--_ptr];
}


int main()
{
	char str_infix[] = "(2+2)*3+5*(7+3)";
	char str_postfix[MAX_LEN];

	cout << str_infix << endl;

	PostfixNotation(str_infix, str_postfix);
	cout << str_postfix << endl;

	return 0;
}

[Elnamir]

Большое спасибо за перевод, но столкнулся с другой проблемой, теперь не могу нормально сделать что бы вычислялось выражение

#include <iostream>
#include <cstring>

using namespace std;


#define MAX_LEN 256
char stack[MAX_LEN];	// стек для хранения операторов при преобразовании
int st_ptr = 0;				// указатель вершины стека

void push(char *_stack, int &_ptr, char data);
char pop(char *_stack, int &_ptr);

//
//	Преобразование записи математ. выражения из инфиксной в постфиксную (в обратную польскую запись)
//
//	Сразу оговоримся, допустимые операторы: +,-,*,/,(,),^; все операции будем считать лево-ассоциативными
//	Все операнды - односимвольные
//
void PostfixNotation(const char *_infix, char *_postfix)
{
 //Тут предыдущая функция
}

void calculation(const char* postfix, char* result)
{
	int in_index = 0;
	int out_index = 0;
	st_ptr = 0;
	int first_numb, two_numb;
	do
	{
		char c = postfix[in_index];
		switch(c)
		{
			char one,two;
			case '+':
				one = pop(stack,st_ptr);
				two = pop(stack,st_ptr);
				first_numb = atoi(&one);
				two_numb = atoi(&two);
				push(stack,st_ptr,(char)(two_numb + first_numb));
				break;
			case '-':
				one = pop(stack,st_ptr);
				two = pop(stack,st_ptr);
				first_numb = atoi(&one);
				two_numb = atoi(&two);
				push(stack,st_ptr,(char)(two_numb - first_numb));
				break;
			case '*':
				one = pop(stack,st_ptr);
				two = pop(stack,st_ptr);
				first_numb = atoi(&one);
				two_numb = atoi(&two);
				push(stack,st_ptr,(char)(two_numb * first_numb));
				break;
			case '/':
				one = pop(stack,st_ptr);
				two = pop(stack,st_ptr);
				first_numb = atoi(&one);
				two_numb = atoi(&two);
				push(stack,st_ptr,(char)(two_numb / first_numb));
				break;
			case '^':
				one = pop(stack,st_ptr);
				two = pop(stack,st_ptr);
				first_numb = atoi(&one);
				two_numb = atoi(&two);
				push(stack,st_ptr,(char)(two_numb ^ first_numb));
				break;
			default:
				push(stack, st_ptr, c);
				break;
		}
		in_index++;
	}while(postfix[in_index] != 0);

	while(st_ptr != 0)
	{
		result[out_index++] = pop(stack,st_ptr);
	}
	result[out_index] = 0;
}
void push(char *_stack, int &_ptr, char data)
{
	_stack[_ptr++] = data;
}

char pop(char *_stack, int &_ptr)
{
	return _stack[--_ptr];
}


int main()
{
	char str_infix[] = "(2+2)*3+5*(5+3)";
	char str_postfix[MAX_LEN];
	char result[MAX_LEN];
	cout << str_infix << endl;
	PostfixNotation(str_infix, str_postfix);
	cout << str_postfix << endl;
	calculation(str_postfix, result);
	cout << result << endl;
	return 0;
}

[nikmoon]

Удали свою функцию calculation. Вместо нее добавь это:

//
// Возведение в степень a^b
//
int pow_int(int a, int b)
{
	int res = a;
	while (b >= 2)
	{
		res = res * a;
		b--;
	}
	return res;
}

int calculation(const char* postfix)
{
	int stack[MAX_LEN];	// стек для хранения операндов
	int st_ptr = 0;		// указатель вершины стека

	int temp;
	int in_index = 0;

	int op_a, op_b;

	do
	{
		char c = postfix[in_index];
		if ((c >= '0') && (c <= '9'))
		{
			temp = c - '0';
		}
		else
		{
			op_b = pop_int(stack, st_ptr);
			op_a = pop_int(stack, st_ptr);

			switch(c)
			{
				case '+':
					temp = op_a + op_b;
					break;
				case '-':
					temp = op_a - op_b;
					break;
				case '*':
					temp = op_a * op_b;
					break;
				case '/':
					temp = op_a / op_b;
					break;
				case '^':
					temp = pow_int(op_a, op_b);
					break;
				default:
					cout << "Unknown operation " << c << endl;
					exit(EXIT_FAILURE);
			}
		}
		push_int(stack, st_ptr, temp);
		in_index++;
	}
	while(postfix[in_index] != 0);

	return pop_int(stack, st_ptr);
}

void push_int(int *_stack, int &_ptr, int data)
{
	_stack[_ptr++] = data;
}

int pop_int(int *_stack, int &_ptr)
{
	return _stack[--_ptr];
}

int main()
{
	char str_infix[] = "(2+2)*3+5*(5+3)";
	char str_postfix[MAX_LEN];

	cout << str_infix << endl;

	PostfixNotation(str_infix, str_postfix);
	cout << str_postfix << endl;

	cout << calculation(str_postfix) << endl;

	return 0;
}