(Infix-to-Post fix conversion) Stacks are used by compilers to help in the process of evaluating expressions and generating machine language code. In this and the next exercise, we investigate how compilers evaluate arithmetic expressions consisting only of Constants, operators and parentheses. Humans generally write expressions like 3 + 4 and 7 / 9 in which the operator ( + or / here) is written between its operands—this is called infix notation. Computers “prefer" postfix notation in which the operator is written to the right of its two operands. The preceding infix expressions would appear in postfix notation as 3 4 + and 7 9 /, respectively. To evaluate a complex infix expression, a compiler would first convert the expression to postfix notation and evaluate the postfix version of the expression. Each of these algorithms requires only a single left-to-right pass of the expression. Each algorithm uses a stack object in support of its operation, and in each algorithm the stack is used lor a different purpose. In this exercise, you’ll write a C++ version of the infix-to-postfix conversion algorithm. In the next exercise, you’ll write a C++ version of the postfix expression evaluation algorithm. Later in the chapter, you’ll discover that code you write in this exercise can help you implement a complete working complier. Write a program that converts an ordinary infix arithmetic expression (assume a valid expression is entered) with single-digit integers such as (6+2) * 5 − 8 / 4 to a postfix expression. The postfix version of the preceding infix expression is 6 2 + 5 * 84 / - The program should read the expression into string infix anti use modified versions of the stack function implemented in this chapter to help create the postfix expression in string postfix. The algorithm for creating a postfix expression is as follows: Push a left parenthesis ' (' onto the stack. Append right parathesis ‘)’ to the end of infix. While the stack is not empty, read infix from left to right and do the following: If the current character in infix is a digit, copy it to the next elements of the postfix. If the current in infix is a left parenthesis, push it onto the stack. If the current character in infix is an operator. Pop operators (if there are any) at the top of (he stack while they have equal or higher precedence than the current operator, and insert the popped operators in postfix. Push the current character in infix onto the stack If the current character in infix is a right parenthesis Pop operators front the top of the stack and insert them in postfix until a left parenthesis is at the top of the stack. Pop (and discard) the left parenthesis from the stack . The following arithmetic operations are allowed in an expression: + addition - subtraction *multiplication / division ^ exponentiation % remainder [Note: We assume left-to-right associativity for all operators in this exercise.] The stack should he maintained with stack nodes, each containing a data member and a pointer to the next stack node. Some of the functional capabilities you may want to provide are: function convertToPostfix that converts the infix expression to postfix notation function is Operator that determines whether c is an operator function precedence that determines whether the precedence of operated is greater than or equal to the precedence of operator 2, and. if so. returns true function push that pushes a value onto the stack e function pop that pops a value off the stack function pop that pops a value off the stack. function stackTop that returns the top value of the stack without popping the stack function isEmpty that determines if the stack is empty function printStack that prints the stack

C++ How to Program (Early Objects Version)

10th Edition

ISBN: 9780134448824

Author: Paul Deitel; Harvey M. Deitel

Publisher: Pearson Education (US)

See similar textbooks

Concept explainers

Literals

A literal in computer science is used to express a fixed value in source code. They cannot be modified. Almost all programs have these fixed values or literals.

Videos

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 19, Problem 19.11E

Chapter 19, Problem 19.13E

Students have asked these similar questions

Consider the following database for some store: Customers (cid, cname, city, discount)Agents (aid, aname, city, percent)Products (pid, pname, city, quantity, price)Orders (ordno, mon, cid, aid, pid, qty, dollars) The relation Customers records the ID (cid), name (cname), location (city) of each customer and a discount percentage (discount) for this customer. The relation Agents records the ID (aid), name (aname), location (city) of each agent and a transaction fee (percent) charged by this agent. The relation Products lists the ID (pid), name (pname), location (city), quantity and price of available products. And finally, the relation Orders contains a unique order number (ordno), the month (mon), customer (cid), agent (aid), product (pid), quantity (qty) of each order as well as the total value (dollars) of the transaction. 1. Express the following query in SQL (a) List customers (names) who do not have discounts but purchased at least one product of price greater than $50. (b) Find…

Consider the following relational schema and briefly answer the questions that follow: Emp(eid: integer, ename: string, age: integer, salary: real) Works(eid: integer, did: integer, pct_time: integer) Dept(did: integer, budget: real, managerid: integer) a. Define a table constraint on Dept that will ensure that all managers have age > 30. b. Write SQL statements to delete all information about employees whose salaries exceed that of the manager of one or more departments that they work in. Be sure to ensure that all the relevant integrity constraints are satisfied after your updates.

Consider the following relations: Student(snum: integer, sname: string, rmajor: string, level: string, age: integer) Class(cname: string, meets_at: time, room: string, fid: integer) Enrolled(snum: integer, cname: string) Faculty(fid: integer, fname: string, deptid: integer) The meaning of these relations is straightforward; for example, Enrolled has one record per student-class pair such that the student is enrolled in the class. 2. Express each of the following integrity constraints in SQL unless it is implied by the primary and foreign key constraint; if so, explain how it is implied. If the constraint cannot be expressed in SQL, say so. For each constraint, state what operations (inserts, deletes, and updates on specific relations) must be monitored to enforce the constraint. (a) Every faculty member must teach at least two courses. (b) Every student must be enrolled in the course called 'Math101'. (c) A student cannot add more than two courses at a time…

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Solution Summary: The author explains how the program converts infix to postfix arithmetic expressions.

Concept explainers

Videos

Want to see the full answer?

Chapter 19 Solutions