Stacks
You should do these exercises as a group and coordinate a time among yourselves for this. At the end of the activity, your group should have created your own set of sample solutions for all of the questions – you may share these with other students.
1. Arithmetic terms
Represent the following terms in all of the following ways (except the one already given, if appropriate):
a. Fully bracketed term with infix operators, e.g. (2+3).
b. Minimally bracketed term with infix operators, e.g. 2+3.
c. Syntax tree.
d. RPN,e.g.23+
The terms are:
1. The standard term: (2 + 3) + (4 – 5)
2. The RPN term: 2 5 + 3 6 – ×
3. The following term in Polish Notation: × × 2 + 5 15 4
4. The fully bracketed term: ((2 + 3) × (6 – 5))
5. The syntax tree below:
+ ×6
+ ×345
12
+
2. Logical terms
RPN can also be used for logical expressions. Instead of numbers, you have the constants 1 and 0 (or T and F if you prefer). Variables (x, y, …) work exactly like constants. AND (∧),
OR (∨), NAND (↑), NOR (↓), XOR (⊕), IF (→) and IFF (↔) work exactly the same as plus and times; NOT (¬) only takes one operand so when evaluating an expression with a stack,
you only pop one value, negate it and push it again.
University of Bristol COMSM1302 bristol.ac.uk
Express the following in RPN:
1. (𝑥∧¬𝑦)∨(¬𝑥∧𝑦).
2. ¬(𝑥↑𝑦)→(𝑧⊕𝑤)
3. Rewrite 𝑥 ∨ 𝑦 using only NAND (↑) operations, then express it in RPN.
4. Convert the following truth table to an expression in DNF, then express it in RPN:
x y z f(x,y,z)
0000 0011 0100 0110 1001 1010 1101 1111
Evaulate the following logical RPN terms: 1. 10∨11⊕¬⊕
2. 1 1 ↓ 1 ↓ 0 1 1 ↓↓↓
3. RPN grammar
1. Consider a valid logical RPN term. If C is the number of times a constant appears in the term (0 or 1), V is the number of times a variable appears in the term, B is the number of times a binary (two-operand) operator appears, and U is the number of times a unary operator appears (e.g. logical NOT). What equation must C, V, B and U satisfy?
Hint: think of what the different kinds of elements do to the stack and what the stack
must look like at the end.
2. Why is the equation you found above not sufficient for an RPN term to be valid (that
is, there are sequences of symbols that satisfy the equation but are not valid RPN
terms)?
3. One way of describing fully bracketed terms is as follows, where only terms that can
be built from these rules are valid. Give a similar list of rules for RPN terms.
a. A constant is a valid term.
b. A variable is a valid term.
c. If o is a binary operator and X, Y are valid terms, then (X o Y) is a valid term.
d. If u is a unary operator and T is a valid term, then (u T) is a valid term.
University of Bristol COMSM1302 bristol.ac.uk
4. C programming exercise
As a group, use the provided stacks.c file to implement RPN evaluation with a stack. A token parser is already implemented for you. You should compile the file with “gcc -Wall -std=c99 stacks.c -o stacks.exe” (leave off the .exe if you are not using windows).
The main function reads a string and splits it into tokens, then it demonstrates how to iterate through the list of tokens in a while loop – in this case to print each one. Try it out by running the program and entering “1 100 + 2 * [ENTER]” for example.
The tokens are in a linked list defined by the following structure:
typedef struct _token {
char type;
int value;
char operator;
struct _token *next;
} token;
The first thing you must do with a token is check the type field, if it is 0 then you have an integer constant in the value field, if it is 1 then you have an operator in the operator field which will be one of the four characters + – * / .
Your group’s task is to implement evaluating expressions:
• Create an array of integers to use as a stack (a fixed size of 100 is fine for this exercise). To keep things simple, use a global variable.
• Implement functions void push(int value) and int pop(). You will probably want to store the current stack height (how many elements are currently on the stack)
somewhere. If you try and push on a full stack or pop from an empty stack, the
functions should print an error message.
• Evaluate the RPN expression in the token linked list by walking through the list and
doing the right thing for each token. (In case of an attempt to divide by zero, print an
error message.)
• Your program should then print(f) the result.
• Note that the token list might be NULL, for example if you pressed ENTER without
entering any tokens.
• At the end of the program, if and only if the token list was not NULL, then you need to
call free_tokens(t) exactly once.
• Test your program by running it with several valid RPN expressions and checking the
result that it produces.
• Also test what happens if you enter an illegal expression like “1 2” or simply “+”. Your
program should print an error message in this case, and not crash. Hint: check the stack height.
If you want an additional challenge, implement the Boolean operations AND, OR, XOR and NOT. To do this, declare “&”, “|”, “^” and “~” as operators in the is_op function, then implement them. Note that in C, “&&” is logical and and “&” is binary and; similarly, “!” is logical not and “~” is binary not – you want the binary, not the logical versions (which operate bit-wise).
University of Bristol COMSM1302 bristol.ac.uk
Listing: stacks.c
/*
* This program parses expressions in RPN according to the following convention:
* – A sequence of digits is a valid token.
* – An operator in [ + – * / ] is a valid token..
* – Tokens may be separated by whitespace.
* If multiple number tokens follow each other, they must be separated by
* whitespace, thus “2 3” is two tokens (the numbers 2 and 3) but “23” is a
* single token for the number 23.
*/
#include
#include
#include
typedef struct _token {
char type; // 0 == constant, 1 == operator
int value; // used if type == 0
char operator; // used if type == 1
struct _token *next; // linked list
} token;
char is_op(char* in) {
if (*in == ‘+’ || *in == ‘-‘ || *in == ‘*’ || *in == ‘/’) {
return 1;
} else {
return 0; }
}
token *allocate_token(char type, token **head, token **last) {
token *t = (token*) malloc(sizeof(struct _token));
t->type = type;
t->next = NULL;
if (*head == NULL) {
*head = t;
*last = t;
} else {
(*last)->next = t;
*last = t; }
return t; }
void free_tokens(token *head) {
if (head == NULL) {
fprintf(stderr, “You attempted to free a null pointer. ”
“Speak to your C unit director about why this is a bad idea.\n”);
}
while (head != NULL) {
token *current = head;
head = head-> next;
free(current);
} }
// Parse the input and return a linked list of tokens, allocated on the heap.
// May return NULL if no tokens were found, or an error was encountered.
token* parse(char *input) {
int position = 1;
token *head = NULL, *last = NULL;
for (;;) {
if (*input == ‘ ‘ || *input == ‘\t’) {
input++; position++;
} else if (*input >= ‘0’ && *input <= '9') {
University of Bristol COMSM1302 bristol.ac.uk
} }
int value = (int) (*input - '0');
input++; position++;
while (*input >= ‘0’ && *input <= '9') {
value *= 10;
value += (int) (*input - '0');
input++; position++;
}
token *t = allocate_token(0, &head, &last);
t->value = value;
} else if (is_op(input)) {
token *t = allocate_token(1, &head, &last);
t->operator = *input;
input++; position++;
} else if (*input == ‘\0’) {
return head;
} else {
fprintf(stderr, “Failed to parse input: at position %i, expected ”
“either a digit, whitespace or an operator but found [%c].\n”,
position, *input);
if (head != NULL) {
free_tokens(head);
}
return NULL;
}
int main() {
char input[1000];
memset(input, 0, 1000);
int i;
char *p;
for (i = 0, p = input; i < 999; i++, p++) {
char c = fgetc(stdin);
if (c == '\n' || c == '\r') {
break; }
*p = c; }
token *t = parse(input);
while (t != NULL) {
if (t->type == 0) {
printf(“token: %i\n”, t->value);
} else {
printf(“token: %c\n”, t->operator);
}
t = t -> next; }
// TODO
return 0; }
University of Bristol
COMSM1302
bristol.ac.uk