Book contents
- Frontmatter
- Contents
- Preface
- PART ONE FOUNDATIONS
- PART TWO DATA STRUCTURES
- 9 Abstract Data Types
- 10 Containers as Abstract Data Types
- 11 Stack and Queue
- 12 Application of Stack
- 13 Lists
- 14 Trees, Heaps, and Priority Queues
- 15 Search Trees
- 16 Hashing and Sets
- 17 Association and Dictionary
- 18 Sorting
- Appendix A Unified Modeling Language Notation
- Appendix B Complexity of Algorithms
- Appendix C Installing and Using Foundations Classes
- Index
12 - Application of Stack
from PART TWO - DATA STRUCTURES
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface
- PART ONE FOUNDATIONS
- PART TWO DATA STRUCTURES
- 9 Abstract Data Types
- 10 Containers as Abstract Data Types
- 11 Stack and Queue
- 12 Application of Stack
- 13 Lists
- 14 Trees, Heaps, and Priority Queues
- 15 Search Trees
- 16 Hashing and Sets
- 17 Association and Dictionary
- 18 Sorting
- Appendix A Unified Modeling Language Notation
- Appendix B Complexity of Algorithms
- Appendix C Installing and Using Foundations Classes
- Index
Summary
The main application of this chapter is algebraic expression evaluation. This is a classic and important problem. An algebraic expression containing single character operands and the four arithmetic operators is input as a string. When numeric values are assigned to each operand our goal is to be able to evaluate the arithmetic expression on the fly. The String representing the arithmetic expression is not known until runtime.
What makes this problem particularly interesting is that the core of the solution requires two stacks, each holding different types of data. The solution illustrates how abstractions (the stack in this case) may be utilized to provide an effective underpinning for the solution to a complex problem.
Algebraic Expression Evaluation
Problem: Develop a Java software application that takes an algebraic expression as an input string. An example of such an algebraic expression is (a + b) * c – d + e * f. After numeric values are assigned to each operand (values for a, b, c, d, e, and f), the algorithm must compute the value of the algebraic expression.
Input: A string representing an algebraic expression involving n operands and an n-tuple representing the values for the operands (i.e., numeric values for each operand).
Output: The value of the expression for the particular n-tuple of input operand values.
Solution of Problem:
1. Conversion from infix to postfix
The first step in solving this problem involves a transformation of the input algebraic expression from infix to postfix representation.
- Type
- Chapter
- Information
- Fundamentals of OOP and Data Structures in Java , pp. 214 - 226Publisher: Cambridge University PressPrint publication year: 2000