#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef enum { _none, _plus, _minus, _mul, _dig, _lt, _gt, _pow, _end } Lexem;
Lexem currentLexem;
int currentPos;
char *expr;
typedef struct pNode
{
char sign[5];
Lexem operator;
struct pNode* left;
struct pNode* right;
} Node;
void print_lexem(Lexem l)
{
switch(l)
{
case _lt: printf("("); break;
case _gt: printf(")"); break;
case _plus: printf("+"); break;
case _minus: printf("-"); break;
case _mul: printf("*"); break;
case _pow: printf("^"); break;
case _end: printf("\n"); break;
}
}
Node* expression();
Node* sum();
Node* mul_pow();
Node* mul();
void next_lexem()
{
currentPos++;
switch(expr[currentPos])
{
case '(': currentLexem = _lt; break;
case ')': currentLexem = _gt; break;
case '+': currentLexem = _plus; break;
case '-': currentLexem = _minus; break;
case '*': currentLexem = _mul; break;
case '^': currentLexem = _pow; break;
case '\0': currentLexem = _end; break;
default: currentLexem = _dig; break;
}
}
Node* expression()
{
Node* child = sum();
Node* res;
if(currentLexem == _plus || currentLexem == _minus)
{
res = malloc(sizeof(Node));
res->left = child;
res->operator = currentLexem;
next_lexem();
res->right = expression();
}
else
{
res = child;
}
return res;
}
Node* sum()
{
Node* child = mul_pow();
Node* res;
if(currentLexem == _mul)
{
res = malloc(sizeof(Node));
res->left = child;
res->operator = currentLexem;
next_lexem();
res->right = sum();
}
else
{
res = child;
}
return res;
}
Node* mul_pow()
{
Node* child = mul();
Node* res;
if(currentLexem == _pow)
{
res = malloc(sizeof(Node));
res->left = child;
res->operator = currentLexem;
next_lexem();
res->right = mul();
}
else
{
res = child;
}
return res;
}
Node* mul()
{
Node* res;
if(currentLexem == _lt)
{
next_lexem();
res = expression();
next_lexem();
}
else
{
if(currentLexem == _dig)
{
res = malloc(sizeof(Node));
res->operator = currentLexem;
int i = 0;
while(currentLexem == _dig)
{
res->sign[i++] = expr[currentPos];
next_lexem();
}
res->sign[i] = '\0';
}
}
return res;
}
void parse_tree(Node *n)
{
if(n->operator == _pow &&
n->left->operator == _minus &&
n->right->operator == _dig &&
!strcmp(n->right->sign,"2"))
{
Node *n1 = malloc(sizeof(Node));
Node *n2 = malloc(sizeof(Node));
Node *n3 = malloc(sizeof(Node));
Node *n4 = malloc(sizeof(Node));
Node *n5 = malloc(sizeof(Node));
Node *n6 = malloc(sizeof(Node));
Node *a = n->left->left;
Node *b = n->left->right;
n1->sign[0] = '2'; n1->sign[1] = '\0'; n1->operator = _dig;
n2->left = a; n2->right = n1; n2->operator = _pow;
n3->left = n1; n3->right = a; n3->operator = _mul;
n4->left = n3; n4->right = b; n4->operator = _mul;
n5->left = n2; n5->right = n4; n5->operator = _minus;
n6->left = b; n6->right = n1; n6->operator = _pow;
n->left = n5; n->right = n6; n->operator = _plus;
}
if(n->operator != _dig)
{
parse_tree(n->left);
parse_tree(n->right);
}
}
void print_tree(Node *n)
{
if(n->operator == _dig)
{
printf("%s", n->sign);
}
else
{
if(n->left->operator != _dig) print_lexem(_lt);
print_tree(n->left);
if(n->left->operator != _dig) print_lexem(_gt);
print_lexem(n->operator);
if(n->right->operator != _dig) print_lexem(_lt);
print_tree(n->right);
if(n->right->operator != _dig) print_lexem(_gt);
}
}
int main()
{
expr = "2";
currentPos = -1;
next_lexem();
Node *root, *new_root;
root = expression();
parse_tree(root);
print_tree(root);
printf("\n");
return 0;
}