In C++, Python or Java: Implement the recursive-descend parser of FCS section 11
ID: 3918131 • Letter: I
Question
In C++, Python or Java: Implement the recursive-descend parser of FCS section 11.6 constructing parse trees of the grammar of balanced parentheses (FCS figure 11.25; students are allowed to use directly the code of FCS section 11.6). After constructing a parse tree your algorithm should compute its height and list all labels in pre-order and post-order. Demonstrate with examples that your code operates properly.
(1) <B> ? epsilon
(2) <B> ? ( <B> ) <B>
Figure 11.25
#define FAILED NULL
typedef struct NODE *TREE;
struct NODE {
char label;
TREE leftmostChild, rightSibling;
};
TREE makeNode0(char x);
TREE makeNode1(char x, TREE t);
TREE makeNode4(char x, TREE t1, TREE t2, TREE t3, TREE t4);
TREE B();
TREE parseTree; /* holds the result of the parse */
char *nextTerminal; /* current position in input string */
void main()
{
nextTerminal = "()()"; /* in practice, a string
of terminals would be read from input */
parseTree = B();
}
TREE makeNode0(char x)
{
TREE root;
root = (TREE) malloc(sizeof(struct NODE));
root->label = x;
root->leftmostChild = NULL;
root->rightSibling = NULL;
return root;
}
TREE makeNode1(char x, TREE t)
{
TREE root;
root = makeNode0(x);
root->leftmostChild = t;
return root;
}
TREE makeNode4(char x, TREE t1, TREE t2, TREE t3, TREE t4)
{
TREE root;
root = makeNode1(x, t1);
t1->rightSibling = t2;
t2->rightSibling = t3;
t3->rightSibling = t4;
return root;
}
Fig. 11.27(a). Auxiliary functions for recursive-descent parser.
620 RECURSIVE DESCRIPTION OF PATTERNS
TREE B()
{
(1) TREE firstB, secondB;
(2) if(*nextTerminal == ’(’) /* follow production 2 */ {
(3) nextTerminal++;
(4) firstB = B();
(5) if(firstB != FAILED && *nextTerminal == ’)’) {
(6) nextTerminal++;
(7) secondB = B();
(8) if(secondB == FAILED)
(9) return FAILED;
else
(10) return makeNode4(’B’,
makeNode0(’(’),
firstB,
makeNode0(’)’),
secondB);
}
else /* first call to B failed */
(11) return FAILED;
}
else /* follow production 1 */
(12) return makeNode1(’B’, makeNode0(’e’));
}
Fig. 11.27(b). Function to construct parse trees for strings of balanced parentheses.
Explanation / Answer
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left
child and a pointer to right child */
struct Node {
int data;
Node *left, *right;
};
/* Helper function that allocates a new node */
Node* newNode(int data)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = node->right = NULL;
return (node);
}
// function to check if paranthesis are balanced
bool areParanthesisBalanced(string expr)
{
stack<char> s;
char x;
// Traversing the Expression
for (int i=0; i<expr.length(); i++)
{
if (expr[i]=='('||expr[i]=='['||expr[i]=='{')
{
// Push the element in the stack
s.push(expr[i]);
continue;
}
// IF current current character is not opening
// bracket, then it must be closing. So stack
// cannot be empty at this point.
if (s.empty())
return false;
switch (expr[i])
{
case ')':
// Store the top element in a
x = s.top();
s.pop();
if (x=='{' || x=='[')
return false;
break;
case '}':
// Store the top element in b
x = s.top();
s.pop();
if (x=='(' || x=='[')
return false;
break;
case ']':
// Store the top element in c
x = s.top();
s.pop();
if (x =='(' || x == '{')
return false;
break;
}
}
// Check Empty Stack
return (s.empty());
}
/* Given a binary tree, print its nodes in preorder*/
void preOrder(Node* node)
{
if (node == NULL)
return;
printf("%d ", node->data);
preOrder(node->left);
preOrder(node->right);
}
/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder(struct Node* node)
{
if (node == NULL)
return;
// first recur on left subtree
printPostorder(node->left);
// then recur on right subtree
printPostorder(node->right);
// now deal with the node
printf("%d ", node->data);
}
// functin to return the index of close parenthesis
int findIndex(string str, int si, int ei)
{
if (si > ei)
return -1;
// Inbuilt stack
stack<char> s;
for (int i = si; i <= ei; i++) {
// if open parenthesis, push it
if (str[i] == '(')
s.push(str[i]);
// if close parenthesis
else if (str[i] == ')') {
if (s.top() == '(') {
s.pop();
// if stack is empty, this is
// the required index
if (s.empty())
return i;
}
}
}
// if not found return -1
return -1;
}
// function to construct tree from string
Node* treeFromString(string str, int si, int ei)
{
// Base case
if (si > ei)
return NULL;
// new root
Node* root = newNode(str[si] - '0');
int index = -1;
// if next char is '(' find the index of
// its complement ')'
if (si + 1 <= ei && str[si + 1] == '(')
index = findIndex(str, si + 1, ei);
// if index found
if (index != -1) {
// call for left subtree
root->left = treeFromString(str, si + 2, index - 1);
// call for right subtree
root->right = treeFromString(str, index + 2, ei - 1);
}
return root;
}
// function takes a string and returns the
// maximum depth nested parenthesis
int maxDepth(string S)
{
int current_max = 0; // current count
int max = 0; // overall maximum count
int n = S.length();
// Traverse the input string
for (int i = 0; i< n; i++)
{
if (S[i] == '(')
{
current_max++;
// update max if required
if (current_max> max)
max = current_max;
}
else if (S[i] == ')')
{
if (current_max>0)
current_max--;
else
return -1;
}
}
// finally check for unbalanced string
if (current_max != 0)
return -1;
return max;
}
// Driver Code
int main()
{
string str = "4(2(3)(1))(6(5))";
Node* root = treeFromString(str, 0, str.length() - 1);
if (areParanthesisBalanced(str))
printf ( "Balanced ");
else
printf ("Not Balanced ");
preOrder(root);
printf (" ");
printPostorder(root);
printf (" ");
printf("%d ",maxDepth(str));
printf (" ");
return 0;
}