1. Use a stack to determine if the expression's parentheses are balanced. develop a stack trace like in our lecture (and page 360) that shows each step using a series of boxes.

((b-2*g)/(a-2)*c)-(4*d)-(7/(e+2)*f)-7)

2. Use a stack to determine if the expression's parentheses are balanced. Develop a stack trace like in our lecture (and page 360) that shows each step using a series of boxes.

(d+((5*a)*(c-(d))*(e-b)/c)-2)

Transcribed Image Text:

360 Chapter 7 Stacks openBrace = aStack.pop() // pop a matching open brace // no matching open brace Input string {a{b}c} else { } balancedSoFar = false // end if } // end if // ignore all characters other than braces } // end while if (balancedSo Far and aStack.isEmpty()) { } aString has balanced braces else { aString does not have balanced braces } // end if Figure 7-3 shows the stacks that result when this algorithm is applied to several simple examples.. It may have occurred to you that a simpler solution to this problem is pos- sible. You need only keep a count of the current number of unmatched open braces. You need not actually store the open braces in a stack. However, the Stack as algorithm executes 1. 2. 3. 4. { { { {a{bc} { { { { {ab}c) 1. push "{" 2. push "{"dis 3. pop 4. pop Stack empty balanced 1. push "{" 2. push "{" 3. pop Stack not empty not balanced FIGURE 7-3 { 1. push "{" 2. pop Stack empty when last ">" encountered not balanced Traces of the algorithm that checks for balanced braces 3. Each time you encounter an open brace, you increment the count; each time you encounter a close brace, you decrement the count. If this count ever falls below zero or if it is greater than zero when the end of the string is reached, the string is unbalanced. 360 Chapter 7 Stacks openBrace = aStack.pop() // pop a matching open brace // no matching open brace Input string {a{b}c} else { } balancedSoFar = false // end if } // end if // ignore all characters other than braces } // end while if (balancedSo Far and aStack.isEmpty()) { } aString has balanced braces else { aString does not have balanced braces } // end if Figure 7-3 shows the stacks that result when this algorithm is applied to several simple examples.. It may have occurred to you that a simpler solution to this problem is pos- sible. You need only keep a count of the current number of unmatched open braces. You need not actually store the open braces in a stack. However, the Stack as algorithm executes 1. 2. 3. 4. { { { {a{bc} { { { { {ab}c) 1. push "{" 2. push "{"dis 3. pop 4. pop Stack empty balanced 1. push "{" 2. push "{" 3. pop Stack not empty not balanced FIGURE 7-3 { 1. push "{" 2. pop Stack empty when last ">" encountered not balanced Traces of the algorithm that checks for balanced braces 3. Each time you encounter an open brace, you increment the count; each time you encounter a close brace, you decrement the count. If this count ever falls below zero or if it is greater than zero when the end of the string is reached, the string is unbalanced. 360 Chapter 7 Stacks openBrace = aStack.pop() // pop a matching open brace // no matching open brace Input string {a{b}c} else { } balancedSoFar = false // end if } // end if // ignore all characters other than braces } // end while if (balancedSo Far and aStack.isEmpty()) { } aString has balanced braces else { aString does not have balanced braces } // end if Figure 7-3 shows the stacks that result when this algorithm is applied to several simple examples.. It may have occurred to you that a simpler solution to this problem is pos- sible. You need only keep a count of the current number of unmatched open braces. You need not actually store the open braces in a stack. However, the Stack as algorithm executes 1. 2. 3. 4. { { { {a{bc} { { { { {ab}c) 1. push "{" 2. push "{"dis 3. pop 4. pop Stack empty balanced 1. push "{" 2. push "{" 3. pop Stack not empty not balanced FIGURE 7-3 { 1. push "{" 2. pop Stack empty when last ">" encountered not balanced Traces of the algorithm that checks for balanced braces 3. Each time you encounter an open brace, you increment the count; each time you encounter a close brace, you decrement the count. If this count ever falls below zero or if it is greater than zero when the end of the string is reached, the string is unbalanced.

Answer rating: 100% (QA)

Solution Step1 1 b2ga2c4d7e2f7 Ans import javautilStack public class BalancedParentheses public stat... View the full answer