Explain what modifications would be needed to make the parenthesis
matching algorithm check expressions with different kinds of
parentheses such as (), [] and {}'s.
Complete the body of this function. You do not need to check the
precondition. You may use the stack template class.
bool balanced(const char p[ ], size_t n)
// Precondition: p[0]...p[n-1] contains n characters, each of which
// is '(', ')', '{' or '}'.
// Postcondition: The function returns true if the characters form a
// sequence of correctly balanced parentheses with each '(' matching
// a ')' and each '{' matching a '}'. Note that a sequence such as
// ( { ) } is NOT balanced because when we draw lines to match the
// parentheses to their partners, the lines cross each other. On the
// other hand, ( { } ) amd { ( ) } are both balanced.
Short Answers Section 7.3 Implementations of the stack ADT
|
I am going to execute this code with THREE pushes and ONE pop:
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
s.pop( );
Suppose that s is represented by a partially filled array. Draw the
state of the private member variables of s after the above code:
_______ __________________________________
used| | data| | | | | |
|_______| |______|______|______|______|______|
[0] [1] [2] [3] [4]
I am going to execute this code with THREE pushes and ONE pop:
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
cout << s.pop( );
Suppose that s is represented by a linked list. Draw the
state of the private member variables of s after the above code:
_______
head_ptr| |
|_______|
Short Answers Section 7.4 More Complex Stack Applications
|
Implement the following function. You may use the stack template class and
the stack operations of push, pop, peek, is_empty, and size.
You may also use cin.peek( ) and use
"cin>>i" to read an integer.
int evaluate_postfix_from_cin( )
// Precondition (Which is not checked): The next input line of cin is a
// properly formed postfix expression consisting of integers,
// the binary operations + and -, and spaces.
// Postcondition: The function has read the next input line (including
// the newline) and returned the value of the postfix expression.
{
int i;
stack<int> s;
Consider the usual algorithm to convert an infix expression to a postfix
expression. Suppose that you have read 10 input characters during
a conversion and that the stack now contains these symbols:
| |
| + |
| ( |
bottom |___*___|
Now, suppose that you read and process the 11th symbol of the input.
Draw the stack for the case where the 11th symbol is:
A. A number:
B. A left parenthesis:
C. A right parenthesis:
D. A minus sign:
E. A division sign: