преобразования польской формы записи уравнения

[Безбашик]

Народ тут такое дело, вообщем курсач дали по теме решение логических уравнений ( например !A&B=A|C ), так вот, программа решает уравнения, но возникла проблема, препод дал мне уравнение записанное в польской форме, и мне нужно написать метод для преобразования польской формы записи уравнения в инфиксную, чтобы прога могла его решить, если у кого есть готовый код или кому не лень помогите =) Что такое польская форма записи объяснять не нужно, мне бы желательно метод чтобы человек дописал.
Для тех кто не понял объясню польская форма записи это когда операнд стоит после переменных самый простой пример AB&=1 и вот программа должна преобразовать его в вид A&B=1 а потом решить. Или к примеру посложнее AB&CD&||=1 метод должен преобразовать эту запись в (A&B) || (C&D)=1
PS Помогите пожалуйста я ж не просто так прошу мне курсовик в понедельник сдавать если не бесплатно то хотя бы за пиво =) Моя не до конца готовая но рабочая программа лежит в архиве.

[alexinspir]

алгоритм в письменном виде:

предположим уравнение вот такого вида:
ab*ab**ab*ab***
где a - первый операнд сравнения, b - второй операнд, * - логическая операция

преобразуем:
((a*b)*(a*b))*((a*b)*(a*b))

анализируем:
1.если за операндом стоит сразу логическая операция, то смещаем операцию на 1 порядок назад(1 порядок == 1 операнд):

ab* => a*b

2.если за операндом сразу два знака, то первый смещаем по методу (1), а второй на два порядка назад:

ab*ab** => a*b*a*b

(здесь и далее для удобства лучше ставить скобки по ходу парсинга - т.е. (a*b)*(a*b))

3. если за операндом сразу три знака, то первые два смещаем по правилам (1) и (2), а третий на 4 порядка:

ab*ab**ab*ab*** == a*b*a*b*a*b*a*b или понятнее: ((a*b)*(a*b))*((a*b)*(a*b))

4. если четыре знака, то на 8 порядков, если более, то каждыый раз удваиваем количество порядков( для 5 - 16, для 6 - 32 etc).

наиболее удобно если ставить скобки приоритета сразу же, чтобы не запутаться.

данный алгоритм подразумевает что вводимое значение будет строкой или массивом(что лучше -- массив объектов типа Object)


а вот как это реализовать - это уже Вам думать - вы же учитесь. а мне лень писать.

Удачи с курсовым проектом!

з.ы. 5 минут потребовалось на обдумывание и минут 15-20 на написание здесь.
Алгоритм только для симметричных выражений!

[Безбашик]

Большое спасибо, легче алгоритма мне не предлагали. Однако, я тут нашёл парочку НО. 1) Что делать с операцией НЕ (её ещё называют отрицание), которая действует на 1 переменную, по какому принципу переставлять её??Например AB&! каким образом это преобразовать? Это будет !(A&B) или !A&B но если один из вариантов то тогда как получить другой? или например AB!& получается тут отрицание и операция И смещаются на 1 позицию оба? Непонятно 2) Скобки нужны обязательно, а можно объяснить как их ставить? А то вручную всё легко и просто, а на джаве я не могу догнать по какому принципу объяснить программе как,что и куда ставить.

[alexinspir]

Сообщение от Безбашик

1) Что делать с операцией НЕ (её ещё называют отрицание), которая действует на 1 переменную, по какому принципу переставлять её??Например AB&! каким образом это преобразовать? Это будет !(A&B) или !A&B но если один из вариантов то тогда как получить другой? или например AB!& получается тут отрицание и операция И смещаются на 1 позицию оба?

надо посмотреть правила записи в польской форме (я кстати первый раз услышал что такая вообще есть)

скорее всего:
AB&! это !(A&B)
A!B& это (!A)&B
AB!& это A&(!B)

посмотрим что из этого может вытекать.
предположим у нас уравнение вот такого вида:
AB&CD&!||
по тем предположениям что я написал, это получается:
(A&B)||(!(C&D))
из этого следует, что знак отрицания надо смещать по правилам, а следующий за ним так как будто знака отрицания небыло
[-- для наглядности перепишу следующий пример без скобок: A&B||!C&D --]

Сообщение от Безбашик

Непонятно 2) Скобки нужны обязательно, а можно объяснить как их ставить? А то вручную всё легко и просто, а на джаве я не могу догнать по какому принципу объяснить программе как,что и куда ставить.

просто вставлять в массив(строку) там где надо. а потом уже писать парсер который будет считать значение в скобках:
для наглядности:
(A&B)||(!(C&D))
анализируем количество скобок, находим последнюю открывающуюся
берем содержимое этой скобки до закрывающейся скобки, а сами скобы выкидываем. итого:
(A&B)||(!(C&D))
значение в последней скобке:
С&D, считаем его, это у нас будет F(предположим).
тогда у нас получается:
(A&B)||(!F)
и так далее пока не кончатся скобки, как кончатся - просто считаем оставшиеся выражения.

для примера, парсер скобок в обычных математических выражениях:

class BracketSniffer //InSpir 10.02.2009 4:00 begin
{
	public static Vector act(Vector v)
	{
		Vector vBuff = new Vector(1,1);
		final char BracketOpen = '(';
		final char BracketClose = ')';
		boolean br = true; //flag
		if(!v.contains(new Character('('))) //if no bracket
		{
			br=false;
		}
		ListIterator vItr = v.listIterator();
		while(br)
		{
			vItr = v.listIterator();
			outer: while(vItr.hasNext())
			{
				char ch; //
				int lastIndex = v.lastIndexOf(new Character('('));
				vItr = v.listIterator(lastIndex);
				ch = (char)(Character)vItr.next();
				if(ch == BracketOpen)
				{
					vItr.remove();
					while(true)
					{
						
						ch = (char)(Character)vItr.next();
						
						if(ch == BracketClose) //if meet close bracket
						{
							
							vItr.remove();
							Stack stt = PlaceToStack.act(vBuff);
							vBuff.removeAllElements();
							Vector vBuff1 = DoubleToChar.act(Calculation.act(stt)); //Calculate inner expression and push it into temp vector
							ListIterator vBuff1Itr = vBuff1.listIterator();
							while(vBuff1Itr.hasNext()) //add result to sourse vector
							{
								char cht = (char)(Character)vBuff1Itr.next();
								vItr.add(new Character(cht));
							}
							break outer;
						}
						vBuff.addElement(new Character(ch));
						vItr.remove();
						
					}
				}
			}
			
			if(!v.contains(new Character('(')))
			{
				br=false;
			}
		}
		return v;
	}
}//InSpir 10.02.2009 4:00 end

[Безбашик]

Извини, видимо некорректно задал вопрос. Я о всё том же преобразовании из польской в инфиксную. Вот ABC&|| это будет (A||(B&C)) вот мне и интересно как заключать выражения в скобки =)

[alexinspir]

Сообщение от Безбашик

Извини, видимо некорректно задал вопрос. Я о всё том же преобразовании из польской в инфиксную. Вот ABC&|| это будет (A||(B&C)) вот мне и интересно как заключать выражения в скобки =)

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

[Безбашик]

Всё спасибо, программа готова.