Algorithm for the infix-to-postfix converter

Assignment Help Data Structure & Algorithms
Reference no: EM131279417

ADT Stack

Objectives

- To gain understanding of how an implementation of an ADT is used by an application program.
- To learn how expressions can be evaluated at run-time.
- To become familiar with how infix expressions can be converted to postfix expressions.

Task

Write a Java program (a collection of Java classes) including a class named ExpressionCalculator that contains a static main method. This main method will prompt the user to enter a constant expression (i.e., a mathematical expression without variables) at the keyboard. The expression must be in infix notation and must use spaces to separate the tokens (operands and operators) of the expression. (This restriction is imposed to simplify the parsing of the input.) The only exception to the space-separation rule is for the unary minus prefix operator, which will be assumed to be part of the specification of a negative constant operand. The program will then evaluate the expression and display the result on the console. It will then wait for another expression to be entered for evaluation, terminating on an empty input.

The following operators should be supported by your expression calculator:

Operator

Type

Precedence

Description

+

binary

4

addition

-

binary

4

subtraction

*

binary

5

multiplication

/

binary

5

division

mod

binary

5

remainder

Operator

Type

Precedence

Description

^

binary

6

exponentiation

!

right unary

6

factorial

%

right unary

6

percentage

abs

unary

6

absolute value

trunc

unary

6

truncation

round

unary

6

rounding

sin

unary

6

sine

cos

unary

6

cosine

ln

unary

6

natural logarithm

log

unary

6

common (base-10) logarithm

lg

unary

6

base-2 logarithm

exp

unary

6

natural exponential (ek)

sqr

unary

6

square (k2)

sqrt

unary

6

square root

The algorithm for the infix-to-postfix converter is as follows:

while there are more tokens in the infix string get the next token
if the next token is an operand append it to the postfix expression
else if the next token is an operator process the operator (see below)
else
indicate a syntax error
pop the remaining operators off the operator stack and append them to the postfix expression, but indicate a syntax error if a '(' is found

The algorithm for processing an operator is:

if the operator stack is empty or
the item on top of the stack is '('

push the current operator onto the stack
else
fetch the top operator on the stack
if the precedence of the current operator is greater than the precedence of the top operator from the stack
push the current operator onto the stack
else
while the stack is not empty and
the operator on top of the stack is not '(' and
the precedence of the current operator is less than or equal to the precedence of the top operator on the stack
pop the top operator off the stack and append it to the postfix

expression

if the operator stack is not empty
fetch the top operator from the stack

if the operator on top of the stack is '(' pop the top element of the stack
if the current operator is not ')'
push the current operator onto the stack

You can also use the algorithms in the text-book if you like. You can also adjust them as needed to allow for the correct processing of right-associative unary operators. If some of those operations cannot be complemented, that is fine.

You can use the algorithm for postfix expression evaluator in the textbook.

Hints

Use a StringBuffer or the new StringBuilder class of Java 5 for the postfix expression as it is being constructed. It is more efficient to make many modifications to a StringBuffer or to append() strings to a StringBuilder than to continually create new Strings by appending to existing ones.

Use Java's StringTokenizer or the new Scanner class of Java 5 to parse expressions. The latter offers the methods hasNextType and nextType (where Type is replaced by Integer, Double, etc.), which would be convenient for checking if the next token in an expression can be parsed as a Double and is thus an operand.

Verified Expert

This assignment deals with the infix expression and convert it to the postfix expression and then evaluate the result. It make the use of the stack to evaluate the expression and it also identify the invalid infix expression.

Reference no: EM131279417

Questions Cloud

Institutional challenges and strategic pressures facing firm : What are the institutional challenges and strategic pressures facing firms doing business in emerging markets generally and Argentina in particular and how might our organization respond to those challenges?
Major component of human resource management : Explains the nature of staffing, giving insight into the major component of human resource management. (The term talent management has become a loose synonym for staffing and human resource management.) If you were a manager interviewing candidates, ..
Risks associated with doing business in emerging markets : What are some political risks associated with doing business in emerging markets generally and Argentina in particular and how might an organization respond to those challenges?
Claim for loss of services by an injured spouse : Ed and Martha are husband and wife. While driving home from work one day Martha is injured in a motor vehicle accident when another driver runs a red light and hits her car. Although he was not in the car and did not suffer any personal injuries, Ed ..
Algorithm for the infix-to-postfix converter : COSC 2006 -Data Structures - Write a Java program (a collection of Java classes) including a class named ExpressionCalculator that contains a static main method. This main method will prompt the user to enter a constant expression
Conventional payment system and capitation : What are the primary differences between a conventional payment system and capitation?- What are the differences in provider incentives under conventional reimbursement and capitation?
Write an eassy about the criminal-case serial murderers : Write an eassy about the criminal and case, a body that discusses the issues surrounding the case (how were they able to avoid being caught for so long - personality of the offender, lack of evidence available, lack of technology, etc.),
What is the purpose of controls : Please,examples of corporate social responsibilities and how it ties to business ethics. Do you think, for Multinational Corporations, using child labor is legal and ethical in less developed economies? What is the purpose of controls? Describe any t..
Determine the diameter of the pipe : A flowrate of 3.5 ft3 /s is to be maintained in a horizontal aluminum pipe (e = 5 ×10-6 ft). The inlet and outlet pressures are 65 psi and 30 psi, respectively, and the pipe length is 500 ft. Determine the diameter of the pipe.

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Write a pseudocode-function to count the number of items

Write a pseudocode/function that will delete from an unsorted linked list of integers the node that contains the smaller integer. Can you do this with a single traversal of the list.

  Explain the binary search tree search algorithm

How do you know if a graph is a binary tree? Explain the preorder traversal algorithm. Explain the binary search tree search algorithm.

  Give an algorithm that takes n lines as input

Give an algorithm that takes n lines as input and in O(n log n) time returns all of the ones that are visible. Figure 5.10 gives an example

  Organize and manage the genealogical tree

Suppose you are asked to develop a program that creates and develops thepedigree of a family. Asked to define the main structures (structures or classes) thatwill organize and manage the genealogical tree so that the program be able to answer at leas..

  In addition make a flow-chart to show how to sort using one

there are many additional algorithms available. choose 2 sorting and 2 searching algorithms and describe them in

  Differentiate between a classic and a thin client platform

Differentiate between a classic and a thin client platform. Suggest a scenario where a thin client would be preferred over a regular desktop and suggest an alternate scenario where a regular desktop would be preferred over a thin client. Describe ..

  Give a recursive algorithm for finding the number of one''s

Give a recursive algorithm for finding the number of one's in a bit string, name the algorothm count-ones.

  Probabilistic analysis of hash functions

Probabilistic Analysis of Hash Functions - In this assignment, you will write and evaluate 5 different hash functions with whose input keys are names. Your evaluation should be based on popular American first names

  Write a program that will perform the same operations twice

Write a program that will perform the same operations twice, once using an array of structs, and once using a pair of parallel arrays. The data will represent people's names and ages, so the first data structure will be an array of structs.

  Describe the scope of the project and control measures

Describe the scope of the project and control measures - describe the goals and objectives of the project and include a high-level overview of all project deliverables.

  Show steps needed to look up ann arbor using binary search

Show steps needed to look up Ann Arbor using binary search on the following list: Ann Arbor, Berkeley, Cambridge, Eugene, Madison, New Haven, Pasadena, Santa Cruz, Stony Brook, Westwood, and Yellow Springs.

  Write a very simple data maintenance java program for a bank

COSC 2006 -Data Structures - Show your program to TA before or on due date, and hand in (at the same time) a printed copy of your program and the output of your program, using the test data posted on the website.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd