Stacks Implemented Using Arrays
TypedefsWe will represent a stack based on the following typedefs:
typedef struct
{
int iCount; // number of elements in stack.
//0 is empty
ElementstackElementM[MAX_STACK_ELEM];
} StackImp;
typedef StackImp *Stack;
The typedef for Element depends on what an element needs.
If it simply needs a numeric type:
typedef int Element;
typedef double Element;
For one C file, only one definition of Element is allowed.
If we want it to be a structure, we can specify
typedef struct
{
char szToken[MAX_TOKEN+1];
int iPrecedence;
int iCategory;
} Element; / // Using double for Element
typedef double Element;
typedef struct
{
int iCount; // number of elements in stack.
//0 is empty
ElementstackElementM[MAX_STACK_ELEM];
} StackImp;
typedef StackImp *Stack;
// To create a stack:
Stack stack;
stack = newStack(); // one of the functions we have to implement
If the element needs to be an array (e.g., simply a string), we cannot do this:
typedef char Element[10];
Why not? What is pop returning? something of type Element
??
If we want an element to be a character string, we must surround it with a structure. This would allow pop to return it.
Important Stack Functions in C
void push (Stack stack, Element value)
pushes the value onto the stack
Element pop (Stack stack)
removes the top element from the stack and returns it
int isEmpty (Stack stack)
returns true if stack is empty
Stack newStack()
allocates, initializes, and returns the stack.
Element topElement(Stack stack)
returns the top of element of the stack without removing it from the stack / // Code for function newStack
StacknewStack()
{
Stackstack = (Stack) malloc(sizeof(StackImp));
stack->iCount = 0; // initially, empty
return stack;
}
// Code for function freeStack
voidfreeStack(Stackstack)
{
free (stack);
}
Array Implementation of push
Some considerations:
- Since we are inserting an element, we must make certain that we don't overflow the array.
- We need to store the push value at
stackElementM[stack->iCount] - We must increment iCount
void push(Stackstack, Elementvalue)
{
if (stack->iCount >= MAX_STACK_ELEM)
ErrExit(ERR_STACK_USAGE
, "Attempt to PUSH more than %d values on the array stack"
, MAX_STACK_ELEM);
stack->stackElementM[stack->iCount] = value;
stack->iCount++;
}
What is happening with Push?
newStack
Push 3
Push 4
What does stack contain? / newStack:
iCount 0
stackElementM
Push 3:
iCount 0 1
stackElementM
3
Push 4:
iCount 1 2
stackElementM
3 / 4
Array Implementation of popand isEmpty
Some considerations:
- Since we want to use an element in the stack, we must make certain the stack isn't empty.
- We must decrement iCount.
- We must return the element at iCount.
Element pop(Stackstack)
{
if (isEmpty(stack))
ErrExit(ERR_STACK_USAGE
, "Attempt to POP an empty array stack");
stack->iCount--;
returnstack->stackElementM[stack->iCount];
}
// code for function isEmpty
int isEmpty(Stackstack)
{
returnstack->iCount <= 0;
}
What is happening with Pop?
Assume stack has two elements 3 and 4.
Pop returns 4
Pop returns 3 / Initially, based on assumption:
iCount 2
stackElementM
3 / 4
Pop returns 4
iCount 2 1
stackElementM
3
Pop returns 3
iCount 1 0
stackElementM
Exercise: Use a stack to determine if an expression has balanced parentheses
Good:
(A (B) D)
( A B D ( E F)(H ) I)
(((A) B))
Bad:
(A B
( (A B)) D)
Use getToken(see program #0)
char * getToken (char *pszInputTxt, char szToken[], int iTokenSize) which examines the input text to return the next token (via szToken). It also functionally returns the position in the text after that token.
Show code for checkParens(char *pszText) returns TRUE if valid.
Get each token:
when '(': ?
when ')': ?
Otherwise: ?
When no more tokens: / typedef char Element; // only need to stack one char
…
intcheckParens(char *pszText)
{
charszToken[MAX_TOKEN];
Stackstack = newStack();
intbValid = TRUE;
pszText = getToken(pszText, szToken, MAX_TOKEN);
while (pszText != NULL)
{
// Use a switch to check for ( and )
switch(szToken[0])
{
case '(':
push(stack, '(');
break;
case ')':
if (isEmpty(stack))
{
bValid = FALSE;
break;
}
pop(stack);
break;
}
pszText = getToken(pszText, szToken, MAX_TOKEN);
}
// stack should be empty
if (isEmpty(stack) != TRUE)
bValid = FALSE;
free(stack);
returnbValid;
}
In the while loop above, why didn't we simply return FALSE instead of setting bValid to FALSE?
??
Infix to Postfix Conversion Including Precedence
Previously we didn't consider precedence in our approach for converting from infix to postfix. Now, we will discuss how to handle precedence. Examples:
A. 3 + 4 * 5 3 4 5 * +
B. 2 * 3 + 4 2 3 * 4 +
C. 12 / 4 * 3 12 4 / 3 *
D. 4 + (5 - 6) * 2 4 5 6 - 2 * +
We will start with example A. Notice that * comes after +, but* has a higher precedence.
Precedence:
higher:* / %
+ -
< > <= >=
== !=
lower:& || / Example A: 3 + 4 * 5:
1. Read 3: Operand so Out 3
Stack
Out: / 3
2. Read +: Operator, stack is empty, so PUSH +
Stack / +
Out: / 3
3. Read 4: Operand so Out 4
Stack / +
Out: / 3 4
4. Read *: ??
Stack
Out:
5. Read 5: ??
Stack
Out:
6. End of Tokens? ??
Stack
Out:
Example B: 2 * 3 + 4
What's the algorithm?
Element element;
for each token left to right:
element.token = token;
categorize(&element);
select token.category:
when operand:
??
when operator:
??
endselect;
endfor;
// no more tokens
while ! isEmpty(stack):
??
endwhile; / Example B: 2 * 3 + 4
1. Read 2: Operand so Out 2
Stack
Out: / 2
2. Read *: PUSH *
Stack / *
Out: / 2
3. Read 3: Operand so Out 3
Stack / *
Out: / 2 3
4. Read +: ??
Stack
Out:
5. Read 4: ??
Stack
Out:
6. End of Tokens: ??
Stack
Out:
Handling Parentheses
Example D: 4 + (5 - 6) * 2
How does that change our code?
Element element;
for each token left to right:
element.token = token;
categorize(&element);
select token.category:
when operand:
??
when operator:
??
when left_paren:
??
when right_paren:
??
endselect;
endfor;
// no more tokens
while ! isEmpty(stack):
??
endwhile; / 4 / + / ( / 5 / - / 6 / ) / * / 2 / no more
stack
- / -
( / ( / (
+ / + / + / +
out / 4 / 5 / 6