Prog 2 0. verseny feladatsor

Ebben a feladatban algebrai kifejezéseket fogunk átalakítani prefix írásmódról hagyományos síkbeli matematikai jelölésre.

Algebrai kifejezésnek tekintjük a következőket: változó, kis szám konstans, két algebrai kifejezés hatványozása, hányadosa, szorzata, különbsége vagy összege.

A prefix írásmódban az operátor jelét az argumentumai elé írjuk. Ennek az az előnye, hogy a jelölés zárójelek nélkül is egyértelmű. Változónak tekintjük az angol ábécé kisbetűit, ezek prefix jelölésben is egyszerűen egy kisbetűbel vannak megadva. Hasonlóan a 0 és 9 közti számokat kis számkonstansnak tekintjük, ezeket a prefix kifejezésben egy számjegy jelzi. (Nagyobb számot nem írunk le.)

Ha x és y két algebrai kifejezés, prefix alakjuk X és Y, akkor értelmes kifejezést kapunk, ha az x-et az y-ik hatványra emeljük, ennek az x^y hatványnak a prefix alakja ^XY. Hasonlóan az x/y hányados, az x*y szorzat, az x-y különbség és az x+y összeg prefix alakje rendre /XY, *XY, -XY, +XY.

Az algebrai kifejezéseknek definiáljuk a hagyományos jelölését is. Ez egy karakterekből álló táblázat, aminek a magasságán és szélességén és a tartalmán kívül még ki van jelölve az egyik sora alapsornak.

A változók és konstansok hagyományos írása egy 1 széles 1 magas táblázat (az alapsor egyértelmű), aminek egyetlen karaktere a megfelelő betű illetve számjegy.

Bonyolultabb kifejezések hagyományos alakját kisebb táblázatok összerakásával kapjuk meg. Ilyenkor az új táblázat pont akkora, hogy az összes összerakott táblázat éppen beleférjen. Ahova semmilyen táblázat nem kerül, ott szóközök állnak.

Hatványozásnál az alap és a kitevő hagyományos alakát úgy rakjuk össze, hogy a kitevőhöz tartozó táblázat bal alsó sarka épp összeérjen az alaphoz tartozó táblázat jobb felső sarkával. A hatvány hagyományos alakjának az alapsora az alap alapsora.

Ha egy algebrai kifejezés két részkifejezés hányadosa, akkor a két részkifejezés hagyományos alakja egymás alá kerül úgy, hogy egy sor kimarad köztük. Vízszintesen úgy kell igazítani a két résztáblázatot, hogy a közepük egymás fölött legyen, vagy, ha ez paritási okból lehetetlen, akkor a szélesebb táblázat közepe 1/2 karakterrel a keskenyebb közepe alatt legyen. A hányados táblázata jobb és bal oldalt is egy oszloppal szélesebb, mint a két rész közül a szélesebbik. Az alapsor az a sor, amelyik a két részkifejezés között szabadon maradt, ezt a sort a táblázatban végig mínusz [-] jelekkel kell feltölteni.

Ha egy algebrai kifejezés két részkifejezés összege, különbsége, vagy szorzata, akkor a két részkifejezés hagyományos alakját úgy kell összerakni, hogy a két rész alapsora ugyanabba a sorba essen, ez lesz az új kifejezés alapsora. Vízszintesen a két résztáblázat között szorzat esetén egy, összeg vagy különbség esetén három oszlopot ki kell hagyni. A szorzat esetén nincs műveleti jel; összegnél és különbségnél a három kihagyott oszlop közül a középsőnek és az alapsornak a metszetébe egy plusz [+] illetve mínusz [-] karaktert kell elhelyezni.

Mielőtt azonban összeraknánk a kifejezéseket, néha még zárójeleket kell beszúrni. Egy hagyományos alakot úgy kell bezárójelezni, hogy a táblázatot bal és jobb oldalt egy-egy oszloppal kibővítjük, ezeket a táblázat teljes magasságában bal [(] illetve jobb [)] zárójelekkel kell kitölteni. Az új táblázat alapsora ugyanaz, ahova a kisebb táblázat alapsora került. Egy kifejezés hagyományos alakját bizonyos esetekben ennek bezárójelezésével kell helyettesíteni, majd az eredeti táblázat helyett ezt használni nagyobb kifejezés építéséhez.

Pontosan a következő esetekben kell zárójelezni. Zárójelezni kell egy szorzatot, hatványt, vagy hányadost, ha egy hatvány alapjában áll; zárójelezni kell egy összeget vagy különbséget, ha ez egy szorzat tényezője vagy egy hatvány alapja. Olyan kifejezésekkel nem foglalkozunk, amiben egy szorzat jobb oldali tényezője szorzat, vagy ahol egy összeg vagy különbség jobb oldali tagja összeg vagy különbség.

Amikor kiírunk egy kifejezést hagyományos alakban, akkor a táblázatot soronként kell kiírni, a sorok végéről a szóközöket elhagyva, és minden sor után újsor jelet kell írni. Végül az egész kifejezés után még egy újsort ki kell írni.

Lássunk egy példát. A következő kifejezést nézzük.

(a/b)^1/2 - (c + d)(1 + a) - (a - d)/b² + b² / (ac)

Ennek a prefix alakja a következő.

+--^/ab/12*+cd+1a/-ad^b2/^b2*ac

A hagyományos alakja egész kifejezésként kiírva pedig az alábbi.

      1
     ---
      2                                  2
( a )                         a - d     b
(---)    - (c + d) (1 + a) - ------- + -----
( b )                           2       a c
                               b

A feladatban a bemenet több sorból áll, minden sorban egy algebrai kifejezés prefix alakja van. A kimenetben ezeknek a kifejezéseknek a hagyományos alakját kell fölrajzolni.

Minden kifejezés olyan, hogy a prefix alakja legfeljebb 100 karakterből áll.

Néhány példa a következő.

z0f7be0 -> z0f7ki0

z0f7be1 -> z0f7ki1

z0f7be2 -> z0f7ki2

Ezt az egyszerűbb feladatot a z0f7.c program oldja meg. Íme a forráskód.

#include 
#include 
#include 

int
max(int x, int y) {
	return x < y ? y : x;
}

#define PLANBUF_LEN 512

#define PREC_ATOM 0
#define PREC_POWER 2
#define PREC_QUOTIENT 3
#define PREC_PRODUCT 4
#define PREC_SUM 5

struct
plan {
	int width;
	int height;
	int depth;
	int prec;
	int head;
	const struct plan *lhs;
	const struct plan *rhs;
} planbuf[PLANBUF_LEN];
int
plancnt;

void
init(void) {
	plancnt = 0;
}

struct plan *
allocplan(void) {
	struct plan *r;
	r = planbuf + plancnt++;
	if (PLANBUF_LEN < plancnt)
		exit(1);
	r->lhs = r->rhs = 0;
	r->prec = r->head = -1;
	r->width = r->height = r->depth = 32767;
	return r;
}

const struct plan *
parenthisize(const struct plan *l) {
	struct plan *p;
	p = allocplan();
	p->head = '(';
	p->lhs = l;
	p->width = l->width + 2;
	p->height = l->height;
	p->depth = l->depth;
	p->prec = PREC_ATOM;
	return p;
}

const struct plan *
layout(const char **formulap) {
	struct plan *p;
	char head;
	const struct plan *l, *r;
	p = allocplan();
	p->head = head = *(*formulap)++;
	if (isdigit(head) || islower(head)) {
		p->width = 1;
		p->height = 1;
		p->depth = 0;
		p->prec = PREC_ATOM;
	} else {
		l = layout(formulap);
		r = layout(formulap);
		if ('^' == head) {
			if (PREC_POWER <= l->prec)
				l = parenthisize(l);
			p->width = l->width + r->width;
			p->height = l->height + r->depth + r->height;
			p->depth = l->depth;
			p->prec = PREC_POWER;
		} else if ('/' == head) {
			p->width = 2 + max(l->width, r->width);
			p->height = 1 + l->height + l->depth;
			p->depth = r->height + r->depth;
			p->prec = PREC_QUOTIENT;
		} else if ('*' == head) {
			if (PREC_PRODUCT < l->prec)
				l = parenthisize(l);
			if (PREC_PRODUCT <= r->prec)
				r = parenthisize(r);
			p->width = 1 + l->width + r->width;
			p->height = max(l->height, r->height);
			p->depth = max(l->depth, r->depth);
			p->prec = PREC_PRODUCT;
		} else if ('+' == head || '-' == head) {
			if (PREC_SUM <= r->prec)
				r = parenthisize(r);
			p->width = 3 + l->width + r->width;
			p->height = max(l->height, r->height);
			p->depth = max(l->depth, r->depth);
			p->prec = PREC_SUM;
		} else 
			exit(1);
		p->lhs = l;
		p->rhs = r;
	}
	return p;
}

#define PAPER_WIDTH 500
#define PAPER_HEIGHT 100

char
paper[PAPER_HEIGHT][PAPER_WIDTH];
int
box_height, box_width;

void
erase(const struct plan *p) {
	int r, c;
	box_height = p->height + p->depth;
	box_width = p->width;
	if (PAPER_HEIGHT < box_height || PAPER_WIDTH < box_width)
		exit(1);
	for (r = 0; r < box_height; r++)
		for (c = 0; c < box_width; c++)
			paper[r][c] = ' ';
}

void
output(void) {
	int r, w, c;
	for (r = 0; r < box_height; r++) {
		w = box_width;
		while (' ' == paper[r][w - 1])
			w--;
		for (c = 0; c < w; c++)
			putchar(paper[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void
paint(const struct plan *p, int row, int col) {
	int r, c;
	int head;
	if (
		row - p->height + 1 < 0 || 
		box_height < row + p->depth ||
		col < 0 ||
		box_width < col + p->width
	)
		exit(1);
	head = p->head;
	switch (head) {
		case '(':
			for (r = row - p->height + 1; r <= row + p->depth; r++) {
				paper[r][col] = '(';
				paper[r][col + p->width - 1] = ')';
			}
			paint(p->lhs, row, 1 + col);
			break;
		case '^':
			paint(p->lhs, row, col);
			paint(p->rhs, row - p->lhs->height - p->rhs->depth, col + p->lhs->width);
			break;
		case '/':
			for (c = col; c < col + p->width; c++)
				paper[row][c] = '-';
			paint(p->lhs, row - 1 - p->lhs->depth, col + (p->width - p->lhs->width)/2);
			paint(p->rhs, row + p->rhs->height, col + (p->width - p->rhs->width)/2);
			break;
		case '*':
			paint(p->lhs, row, col);
			paint(p->rhs, row, 1 + col + p->lhs->width);
			break;
		case '+': case '-':
			paint(p->lhs, row, col);
			paper[row][1 + col + p->lhs->width] = head;
			paint(p->rhs, row, 3 + col + p->lhs->width);
			break;
		default:
			if (isdigit(head) || islower(head))
				paper[row][col] = head;
			else
				exit(1);
			break;
	}
}

void
paint_main(const struct plan *p) {
	paint(p, p->height - 1, 0);
}

#define FORMULA_LEN 512

int
main(void) {
	char formulabuf[FORMULA_LEN];
	const struct plan *p;
	const char *formula;
	while (fgets(formulabuf, FORMULA_LEN, stdin)) {
		formula = formulabuf;
		init();
		p = layout(&formula);
		if ('\n' != *formula)
			exit(1);
		erase(p);
		paint_main(p);
		output();
	}
	return 0;
}

A kód megértéséhez a következőt kell tudni. Minden kifejezést két lépésben dolgozunk fel.

Az első lépésben, amit a layout függvény hajt végre, értelmezzük a prefix kifejezést, és minden részkifejezéséhez csinálunk egy struct plan típusú leírót. A leíróban eltárolunk elég információt ahhoz, hogy a kifejezés visszaállítható legyen, erre szolgálnak a head, lhs, rhs mezők; valamint az ehhez tartozó hagyományos kifejezés méretét is eltároljuk: a width mező a tábla szélességét tartalmazza, a height mező a magasságot az alapsortól a táblázat tetejéig, a depth pedig a mélységet az alapsor alatt. A prec mezőt arra használjuk, hogy eldöntsük, kell-e zárójelezni a kifejezést, ha igen, akkor a zárójelezett változathoz egy újabb leírót hozunk létre.

A második fázisban a leírókat bejárva kirajzoljuk a kifejezéseket. A paper karakter-mátrixba kerül az eredmény: ennek elég nagy részét kitöltjük szóközökkel, majd rekurzívan hívjuk a paint eljárást, ami egy leírót és a részkifejezés alapsorának a bal szélső mezőjének pozícióját kapja argumentumként, és a papar mátrixra rajzol. Végül a mátrix alapján kiírjuk az eredményt.

Mármost önnek azzal kell bővíteni a programot, hogy faktoriálist is kezeljen. Az új szabályok a következők.

Ha x algebrai kifejezés, amelynek X a prefix alakja, akkor x! (azaz x faktoriális) is algebrai kifejezés, és ennek prefix alakja !X. Ha az x részkifejezésnek megtaláltuk a hagyományos alakját, akkor az x! hagyományos alakját úgy kapjuk, hogy az előbbihez hozzárakunk még egy oszlopot jobbra, és ebbe az oszlopba az alapsorba (ami a részkifejezésnek és a teljesnek is az alapsora), rakunk egy felkiáltójel [!] karaktert. Előbb azonban a részkifejezéshez tartozó táblázatot zárójelbe kell rakni, ha ez a részkifejezés hatvány, hányados, szorzat, összeg, vagy különbség. A teljes faktoriálist sosem kell zárójelbe rakni.

Példák.

z0f3be0 -> z0f3ki0

z0f3be1 -> z0f3ki1

A módosított feladat megoldását a SIO-ra a z0f3 feladathoz töltse föl.