Логическая ошибка "Обратной польской записи" - Общие вопросы C/C++

Fanyuus · 21.05.2013, 20:39

Добрый вечер, уважаемые программисты и любители логических задач!

Условие задачи: написать программу, которая обычное выражение (числовое) с использованием "(", ")", "+", "-", "*" и "/", переведёт в польскую запись. Например, 2+34*45+23 = 2 34 45 * + 23 +.

Когда мой однокурсник реализовал такое дело, преподаватель спросил "а как ты 100 представишь, что это 100?", поэтому, я подумала разделять числа и знаки запятыми.

И вроде бы весь механизм реализован, однако скобки вызвали массу проблем.

А именно: (проблемы)

1*2*3, то одного из знаков не выдаёт. И проверяю через точки остановки, но понять всё равно не могу "куда делся ещё один знак?!".
Так же выходит, если напечатать 1*2+3. --> 1,2,*,3

Если ввести строчку: 1+2+3+;+5*6, то всё работает корректно.
Контрольные примеры: 1+(2+3), 1+(2*3), 1*(2+3), 1*(2*3) -- раньше были на них ошибки, сейчас всё работает хорошо.

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

Fanyuus · 21.05.2013, 20:39

Код:


// пол дер 2.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <conio.h>
#include <iostream>
#include <math.h>
#include <Windows.h>
#include <string>
#include <vector>

using namespace std;



/*

Для справки: обозначение знаков в десятичной по таблице ASCII

( = 40 - скобка открывающая
) = 41 - скобка закрывающая
* = 42 - умножить 
+ = 43 - плюс
, = 44 - разделение символов
- = 45 - минус
/ = 47 - деление вариант 1
0 = 48 - цифры
1 = 49
2 = 50
3 = 51
4 = 52
5 = 53
6 = 54
7 = 55
8 = 56
9 = 57 - цифры

*/


void main()
{
	setlocale (0,"");
	char a[255];
	char b[200];
	int t,i,t2,y,d,s; // y = длина вектора C,  a - наращивание строчки для вставки "зпт"
	cout << "Введите выражение: ";
	cin >> b;
	t2=strlen(b); //получили длину строки
	vector<char> C;
	d=0;
	for(i=0; i<t2; i++)
	{
		if ((b[i]=='0')||(b[i]=='1')||(b[i]=='2')||(b[i]=='3')||(b[i]=='4')||(b[i]=='5')||(b[i]=='6')||(b[i]=='7')||(b[i]=='8')||(b[i]=='9'))
		{
			a[i+d]=b[i];
		}
		else
		{
			y=C.size();
			if (y==0)
			{
				C.push_back(b[i]);
				if (C[0]=='(')
				{
					d--;
				}
				if (C[0]==')')
				{
					C.pop_back();
					
				}
				if (a[i+d-1]!=44)
					a[i+d]=',';
					
						
			}
			else
			{
				y=C.size();
				if (b[i]!='(') 
				{
					if ((C[C.size()-1]=='*')||(C[C.size()-1]=='/'))
					{
						while ((y>0)&&((C[C.size()-1]=='*')||(C[C.size()-1]=='/')))
						{
							a[i+d]=',';
							d++;
							a[i+d]=C[C.size()-1];
							d++;
							C.pop_back();
							y--;
						}
						a[i+d]=',';
						if (b[i]!=')')
						{
							y=C.size();
							while ((y>0)&&(C[C.size()-1]!='('))
							{
								a[i+d]=',';
								d++;
								a[i+d]=C[C.size()-1];
								d++;
								C.pop_back();
								y--;
							}
							if (y>0)
							{
								C.pop_back(); // вычли "("
								a[i+d]=',';
							}
						}
					}
					else
					{
						y=C.size();
						if ((y>0)&&((b[i]==42)||(b[i]==47)))
						{
							while((y>0)&&((b[i]==42)&&(C[C.size()-1]==42)||(b[i]==42)&&(C[C.size()-1]==47)||(b[i]==47)&&(C[C.size()-1]==47)||(b[i]==47)&&(C[C.size()-1]==42)))
							{
								a[i+d]=',';
								d++;
								a[i+d]=C[C.size()-1];
								d++;
								C.pop_back();
								y--;
							}
						a[i+d]=',';
						C.push_back(b[i]);
						}
					}
					y=C.size();
					if ((y>0)&&((b[i]==43)||(b[i]==45)))
					{
						while((y>0)&&((b[i]==43)&&(C[C.size()-1]==43)||(b[i]==43)&&(C[C.size()-1]==45)||(b[i]==45)&&(C[C.size()-1]==45)||(b[i]==45)&&(C[C.size()-1]==43)))
						{
							a[i+d]=',';
							d++;
							a[i+d]=C[C.size()-1];
							d++;
							C.pop_back();
							y--;
						}
						a[i+d]=',';
						C.push_back(b[i]);
					}
					if (b[i]==')')
							{
								y=C.size();
								while ((y>0)&&(C[C.size()-1]!='('))
								{
									a[i+d]=',';
									d++;
									a[i+d]=C[C.size()-1];
									d++;
									C.pop_back();
									y--;
								}
								C.pop_back(); // вычли "("
								a[i+d]=',';
								
							}
				}
				else
				{
					y=C.size();
					if ((y>0)&&((b[i]==43)&&(C[C.size()-1]==43)||(b[i]==43)&&(C[C.size()-1]==45)||(b[i]==45)&&(C[C.size()-1]==45)||(b[i]==45)&&(C[C.size()-1]==43)))
					{
						while((y>0)&&((b[i]==43)&&(C[C.size()-1]==43)||(b[i]==43)&&(C[C.size()-1]==45)||(b[i]==45)&&(C[C.size()-1]==45)||(b[i]==45)&&(C[C.size()-1]==43)))
						{
							a[i+d]=',';
							d++;
							a[i+d]=C[C.size()-1];
							d++;
							C.pop_back();
							y--;
						}
						a[i+d]=',';
						C.push_back(b[i]);
					}
					else
					{
						s=56;
						if ((C[C.size()-1]=='(')||(b[i]==')'))
						{
							if (C[C.size()-1]=='(')
							{
								if (b[i]!=')')
								{
									C.push_back(b[i]);
									if (a[i+d-1]!=',')
									{
										a[i+d]=',';
									}
									
								}
								
							}
							if (b[i]==')')
							{
								y=C.size();
								while ((y>0)&&(C[C.size()-1]!='('))
								{
									a[i+d]=',';
									d++;
									a[i+d]=C[C.size()-1];
									d++;
									C.pop_back();
									y--;
								}
								C.pop_back(); // вычли "("
								a[i+d]=',';
							}
						}
						else
						{
							C.push_back(b[i]);
							a[i+d]=',';
							if (a[i+d-1]==',')
									{
										d--;
									}
						}
					}
				}
			}
		}
	}
	y=C.size();
	while (y>0)
	{
		if (a[i+d-1]!=',')
		{
			a[i+d]=',';
			d++;
		}
		a[i+d]=C[C.size()-1];
		d++;
		C.pop_back();
		y--;
	}
	t=0;
	for (i=0; a[i]!=-52; i++)
	{
		t++;
	}
	cout <<  "\n\n";
	for (i=0; i<t; i++)
	{
		cout << a[i];
	}
	cin.get();
	cin.get();
}

Abstraction · 21.05.2013, 20:45

Ой. А функции в... этом... выделить можно?

Код:

(b[i]=='0')||(b[i]=='1')||(b[i]=='2')||(b[i]=='3')||(b[i]=='4')||(b[i]=='5')||(b[i]=='6')||(b[i]=='7')||(b[i]=='8')||(b[i]=='9')

Это называется is_digit(b[i]).

Код:

(b[i]==42)||(b[i]==47)

Это называется "что это, Бэрримор?".
В общем, разобраться в этом почти нереально, такой код надо не модифицировать, его надо выкидывать и писать заново.

Fanyuus · 21.05.2013, 21:20

Аааа, забыла комментарии)))

Цитата:

Ой. А функции в... этом... выделить можно?

надо бы. Хм-хм-хм... Вся суть такая, что это часть калькулятора, который потом ещё и считать будет. Ужс-ужс))

Код:

void main()
{
	setlocale (0,"");
	char a[255]; // строчка-вывод, итоговый результат
	char b[200]; //начальный ввод строчки
	int t,i,t2,y,d,s; // y = длина вектора C,  a - наращивание строчки для вставки "зпт"
	cout << "Введите выражение: ";
	cin >> b;
	t2=strlen(b); //получили длину строки
	vector<char> C; //вектор для сохранения "знаков" из строчки b в строчку а
	d=0; // если мы поставим в строчку а зпт, то индекс d ув. на 1, чтобы ритмично считалось))
	for(i=0; i<t2; i++) //основной цикл, который посимвольно считывает b
	{
		if ((b[i]=='0')||(b[i]=='1')||(b[i]=='2')||(b[i]=='3')||(b[i]=='4')||(b[i]=='5')||(b[i]=='6')||(b[i]=='7')||(b[i]=='8')||(b[i]=='9')) 
		{ //если цифры, то записываем их в а
			a[i+d]=b[i];
		} 
		else // если символ был не цифрой, то 
		{
			y=C.size(); //вычисляем размер вектора
			if (y==0) //если размер вектора равен нулю, то
			{
				C.push_back(b[i]); //добавляем в него новый элемент
				if (C[0]=='(') //если новый элемент был скобкой (в векторе), то d минусуем, т.к., в ОПЗ не может быть скобок
				{
					d--;
				}
				if (C[0]==')') //если новый элемент был обратной скобкой, то его нужно удалить
				{
					C.pop_back();
					
				}
				if (a[i+d-1]!=44) //если предыдущий символ в а не равен зпт, то ставим зпт
					a[i+d]=',';
					
						
			}
			else //если размер вектора не 0, то
			{
				y=C.size(); //ещё раз узнали размер
				if (b[i]!='(') //если текущий элемент в строчке b не равен скобке, то
				{
					if ((C[C.size()-1]=='*')||(C[C.size()-1]=='/')) // если последний элемент в векторе равен умножению или делению, то 
					{
						while ((y>0)&&((C[C.size()-1]=='*')||(C[C.size()-1]=='/'))) //пока длина вектора больше 0 и мы встречаем умножение или деление в векторе, то 
						{
							a[i+d]=',';
							d++;
							a[i+d]=C[C.size()-1]; // этот элемент из вектора переписываем в строчку
							d++;
							C.pop_back(); //а затем его (элемент) удаляем
							y--;
						}
						a[i+d]=',';
						if (b[i]!=')') // если текущий элемент в b не равен закрывающей скобке, то 
						{
							y=C.size(); //вычислили размер вектора
							while ((y>0)&&(C[C.size()-1]!='(')) //пока размер вектора больше 0 и текущий элемент вектора не равен открывающей скобке
							{
								a[i+d]=',';
								d++;
								a[i+d]=C[C.size()-1]; //записываем в строчку а элемент  из вектора
								d++;
								C.pop_back(); // элемент из вектора удаляем
								y--;
							}
							if (y>0) //если размер вектора больше нудя, то
							{
								C.pop_back(); // вычли "("
								a[i+d]=',';
							}
						}
					}

Fanyuus · 21.05.2013, 21:40

Код:


                                        else // если последний элемент в векторе не равен умножению\делению
					{
						y=C.size(); //посчитали размер вектора
						if ((y>0)&&((b[i]==42)||(b[i]==47))) //если размер вектора больше нуля и текущий элемент в строчке b равен умножению или делению, то 
						{
							while((y>0)&&((b[i]==42)&&(C[C.size()-1]==42)||(b[i]==42)&&(C[C.size()-1]==47)||(b[i]==47)&&(C[C.size()-1]==47)||(b[i]==47)&&(C[C.size()-1]==42))) // чёт я сейчас не поняла - из условия, что здесь, ваил работает до тех пор, пока оба элемента совпадают, он это всё дело выкидывает
							{
								a[i+d]=',';
								d++;
								a[i+d]=C[C.size()-1];
								d++;
								C.pop_back();
								y--;
							}
						a[i+d]=',';
						C.push_back(b[i]); // добавили элемент в вектор из b в вектор
						}
					}
					y=C.size(); //посчитали размер вектора 
					if ((y>0)&&((b[i]==43)||(b[i]==45))) //если текущий элемент в строчке b равен сложению или вычитанию, то
					{
						while((y>0)&&((b[i]==43)&&(C[C.size()-1]==43)||(b[i]==43)&&(C[C.size()-1]==45)||(b[i]==45)&&(C[C.size()-1]==45)||(b[i]==45)&&(C[C.size()-1]==43))) //ваил работает до тех пор, пока оба элемента совпадают, он это всё дело выкидывает
						{
							a[i+d]=',';
							d++;
							a[i+d]=C[C.size()-1];
							d++;
							C.pop_back();
							y--;
						}
						a[i+d]=',';
						C.push_back(b[i]); //добавляем текущий элемент из b в вектор
					}
					if (b[i]==')') // если текущий элемент равен закрывающей скобке, то 
							{
								y=C.size(); // посчитали размер вектора
								while ((y>0)&&(C[C.size()-1]!='(')) //ваил работает до тех пор, пока размер вектора больше 0 и элемент в векторе не равен открывающей скобке, которая там находилась
								{
									a[i+d]=',';
									d++;
									a[i+d]=C[C.size()-1];
									d++;
									C.pop_back();
									y--;
								}
								C.pop_back(); // вычли "("
								a[i+d]=',';
								
							}
				}
				else // если текущий элемент равен открывающей скобке, то 
				{
					y=C.size(); // посчитали текущий размер вектора
					if ((y>0)&&((b[i]==43)&&(C[C.size()-1]==43)||(b[i]==43)&&(C[C.size()-1]==45)||(b[i]==45)&&(C[C.size()-1]==45)||(b[i]==45)&&(C[C.size()-1]==43))) //если текущий элемент в b и в векторе + или -, то
					{
						while((y>0)&&((b[i]==43)&&(C[C.size()-1]==43)||(b[i]==43)&&(C[C.size()-1]==45)||(b[i]==45)&&(C[C.size()-1]==45)||(b[i]==45)&&(C[C.size()-1]==43)))  //удаляем до тех пор, пока не встретим скобку или не дойдём до нуля
						{
							a[i+d]=',';
							d++;
							a[i+d]=C[C.size()-1];
							d++;
							C.pop_back();
							y--;
						}
						a[i+d]=',';
						C.push_back(b[i]); // добавили текущий элемент из строчки b в вектор
					}
					else //если текущий b и вектора не + и - и не совпали
					{
						if ((C[C.size()-1]=='(')||(b[i]==')')) //если текущий элемент в векторе равен открывающей скобке, или текущий элемент b равен закрывающей скобке, то
						{
							if (C[C.size()-1]=='(') //если открывающей скобке в векторе, то
							{
								if (b[i]!=')') //если текущий элемент в строчке b не равен закрывающей скобке, то 
								{
									C.push_back(b[i]); //добавили элемент
									if (a[i+d-1]!=',')
									{
										a[i+d]=',';
									}
									
								}
								
							}
							if (b[i]==')') //если текущий элемент строчки b равен закрывающей скобке, то
							{
								y=C.size(); //посчитали размер вектора
								while ((y>0)&&(C[C.size()-1]!='(')) //пока размер вектора больше 0 и мы не встретили открывающую скобку
								{ //записываем элемент из вектора в строчку а
									a[i+d]=',';
									d++;
									a[i+d]=C[C.size()-1];
									d++;
									C.pop_back();
									y--;
								}
								C.pop_back(); // вычли "("
								a[i+d]=',';
							}
						}
						else //если текущий элемент в векторе не равен открывающей скобке и текущий элемент в строчке b не равен закрывающей скобке, то просто добавляем элемент в вектор
						{
							C.push_back(b[i]); 
							a[i+d]=',';
							if (a[i+d-1]==',')
									{
										d--;
									}
						}
					}
				}
			}
		}
	}

Fanyuus · 22.05.2013, 11:43

Помогите, пожалуйста

Abstraction · 22.05.2013, 12:15

Если Вы сами не можете проанализировать и отладить этот код, то, ИМХО, это безнадёжно.

Вот пример моего кода (тоже писался как write-only, для вот этой задачи):

Код:

#include <stdio.h>

int transform(char** expression, char** transformed, int priority);
inline int SignPriority(char sign);
inline int isalpha(char c){
	static const char letters[]="abcdefghijklmnopqrstuvwxyz";
	for(int i=0; i<26;++i) if(letters[i]==c) return 1;
	return 0;
}

int main(void)
{
	char expression[401];
	char transformed[401];
	char* transCpy, *expCpy;
	int expNum;
	for(scanf("%d", &expNum);expNum>0; --expNum){
		transCpy=transformed;
		expCpy=expression;
		scanf("%s", &expression);
		transform(&expCpy, &transCpy, 0);
		printf("%s\n", transformed);
	}
	return 0;
}

//called with expression on operand
//ending when expression on sign or ended
int transform(char** expression, char** transformed, int priority){
	int pr;
	char cur=**expression; 
	while (cur!=')'){
		//operand
		if(cur=='('){
			++*expression;
			if(transform(expression, transformed, 0)==0) return 0;
		}else if(isalpha(cur)){
			**transformed=cur;
			++*transformed;
		}//else error
		cur=*(++*expression);
		//operation
		if((pr=SignPriority(cur))!=-1){
			//found end of current expression part
			if(pr<priority) return 1;
			//second operand
				//move to operand
				++*expression;
				transform(expression, transformed, pr);
			**transformed=cur;
			++*transformed;
			cur=**expression;
		}
		//end
		if(cur=='\0') {
			**transformed='\0';
			return 0;
		}
	}
	return 1;
}

inline int SignPriority(char sign){
	static const char signs[]="+-*/^";
	for(int i=0; i<5; ++i) if(sign==signs[i]) return i;
	return -1;
}

Fanyuus · 22.05.2013, 17:53

Abstraction, исправила я несколько ошибок. Исправила, исправила, и у меня вдруг случайно при написании выражения (7+5) вдруг стало писать:

Цитата:

Run-Time Check Failure #2 - Stack around the variable 'a' was corrupted.

И именно тогда, когда используются скобки.
но ответ правильный выдаёт.

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

Ладно, перепишу свой код в функции, и сделаю не строчку, а массив, наверное. А то мне эта строчка не нравится как-то.

Большое спасибо за код!

Fanyuus · 22.05.2013, 17:55

Abstraction, а что в вашей программе нужно вводить? Просто я ввожу числа\буквы (выражение, 7+2), а в ответ тишина. Или он, код, программа, ничего не выводит в итоге?

ред.: всё, поняла. Там всё дело в скобках)))

Abstraction · 22.05.2013, 18:42

Цитата:

Abstraction, а что в вашей программе нужно вводить?

См. ссылку на задание. Число выражений, затем сами выражения.

Цитата:

Исправила, исправила, и у меня вдруг случайно при написании выражения (7+5) вдруг стало писать:

Вероятно, выход за пределы массива.

21.05.2013, 20:39	#1
Fanyuus Форумчанин Регистрация: 07.05.2011 Сообщений: 169	Логическая ошибка "Обратной польской записи" Добрый вечер, уважаемые программисты и любители логических задач! Условие задачи: написать программу, которая обычное выражение (числовое) с использованием "(", ")", "+", "-", "" и "/", переведёт в польскую запись. Например, 2+3445+23 = 2 34 45 * + 23 +. Когда мой однокурсник реализовал такое дело, преподаватель спросил "а как ты 100 представишь, что это 100?", поэтому, я подумала разделять числа и знаки запятыми. И вроде бы весь механизм реализован, однако скобки вызвали массу проблем. А именно: (проблемы) 123, то одного из знаков не выдаёт. И проверяю через точки остановки, но понять всё равно не могу "куда делся ещё один знак?!". Так же выходит, если напечатать 12+3. --> 1,2,,3 Если ввести строчку: 1+2+3+;+56, то всё работает корректно. Контрольные примеры: 1+(2+3), 1+(23), 1(2+3), 1(23) -- раньше были на них ошибки, сейчас всё работает хорошо. Пожалуйста, помогите исправить эти ошибки. Последний раз редактировалось Fanyuus; 21.05.2013 в 20:42.*

21.05.2013, 20:45	#3
Abstraction Старожил Регистрация: 25.10.2011 Сообщений: 3,178	Ой. А функции в... этом... выделить можно? Код: `(b[i]=='0')\|\|(b[i]=='1')\|\|(b[i]=='2')\|\|(b[i]=='3')\|\|(b[i]=='4')\|\|(b[i]=='5')\|\|(b[i]=='6')\|\|(b[i]=='7')\|\|(b[i]=='8')\|\|(b[i]=='9')` Это называется is_digit(b[i]). Код: `(b[i]==42)\|\|(b[i]==47)` Это называется "что это, Бэрримор?". В общем, разобраться в этом почти нереально, такой код надо не модифицировать, его надо выкидывать и писать заново.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Вопросы по обратной польской записи	АлексВ	Паскаль, Turbo Pascal, PascalABC.NET	8	01.06.2012 11:29
Ошибка "Expecting a valid name" для оператора "<" в JScript	Ратибор Редоран	JavaScript, Ajax	0	15.12.2011 14:38
Ошибка:является "поле" но используется как "метод"	hitman47IT	Помощь студентам	0	22.11.2011 20:55
Логическая структура "Архив"	Vov4k	Помощь студентам	1	14.05.2011 07:15
Ошибка при использовании OlePropertyGet("Documents").OleProcedure("Add") в C++ Builder	AleksP	C++ Builder	7	11.04.2009 13:06

22.05.2013, 11:43	#6
Fanyuus Форумчанин Регистрация: 07.05.2011 Сообщений: 169	Помогите, пожалуйста

22.05.2013, 17:55	#9
Fanyuus Форумчанин Регистрация: 07.05.2011 Сообщений: 169	Abstraction, а что в вашей программе нужно вводить? Просто я ввожу числа\буквы (выражение, 7+2), а в ответ тишина. Или он, код, программа, ничего не выводит в итоге? ред.: всё, поняла. Там всё дело в скобках)))