Program For Evaluating Postfix Expression Using Stack

Write a C Program to convert infix to postfix and evaluate postfix expression. Here’s simple Program to convert infix to postfix and evaluate postfix expression in C Programming Language.

• Program For Evaluation Of Postfix Expression Using Stack In Java

What is Stack ?

Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects.

Basic Operations : :

• push() − Pushing (storing) an element on the stack.

Also Read: Infix to Postfix Conversion in C Program and Algorithm Algorithm for Evaluation of Postfix Expression. Create an empty stack and start scanning the postfix expression from left to right. If the element is an operand, push it into the stack. If the element is an operator O, pop twice and get A and B respectively. Calculate BOA.

• pop() − Removing (accessing) an element from the stack.

• peek() − get the top data element of the stack, without removing it.

• isFull() − check if stack is full.

• isEmpty() − check if stack is empty.

Below is the source code for C Program to convert infix to postfix and evaluate postfix expression which is successfully compiled and run on Windows System to produce desired output as shown below :

SOURCE CODE : :

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.

Thanks for reading the post….

write a C program that will evaluate an infix expression and itshould finished by using the follow example code. The algorithmREQUIRED for this program will use two stacks, an operator stackand a value stack. Both stacks MUST be implemented using a linkedlist.

For this program, you are to write functions for the linked liststacks with the following names:

int isEmpty (stack); void push (stack, data); data top(stack);
void pop (stack);

// return TRUE if the stack has no members
// add the data to the top of the stack
// return the data value on the top of the stack
// remove the data value from the top of the stack

The exact type of each parameter (including the type ofparameter passing being used) is left up to you as the programmer.You may also wish to write a “topPop( )” function that does boththe top and pop operations in a single function. Also, an init( )function and a reset( ) function may prove useful.

These functions must take the head of the linked list (or astructure containing the head of the linked list) as its FIRSTparameter. The actual head of each linked list MAY NOT BE A GLOBALVARIABLE. It MUST be somehow declared as a local variable to somefunction (it may be as a local variable to a function other thanmain). Each operation performed on the linked list MUST be done inits own function.

Please note that you will need a stack of integer values and astack of character operators for this project. However, since theoperators can all be represented as characters (which is asub-class of integers), you are more than welcome to write a singlelinked list structure to be used for both stacks.

The commands used by this system are listed below and are tocome from standard input. Your program is to prompt the user forinput and display error messages for unknown commands. The code inproj3base.c already does this for you. It is expected that you willuse this code as the starting point for your project.

The <infixExpression> will only use the operators ofaddition, subtraction, multiplication, division and theparentheses. It will also only contain unsigned (i.e. positive)integer values. We obviously could allow for more operators andmore types of values, but the purpose of this assignment is tofocus on linked list structures and not on complicated arithmeticexpressions.

Infix Expression are when the operators of addition,subtraction, multiplication and division are listed IN between thevalues. Infix Expressions require the use of parentheses to expressnon- standard precedence. Examples of Infix Expressions are:

42 + 64
60 + 43 * 18 + 57 (60 + 43) * (18 + 57) 18 – 12 – 3
18 – (12 – 3)

Infix Expressions are normally converted to a Postfix Expressionin order to be evaluated. Postfix Expressions are when theoperators of addition, subtraction, multiplication and division arelist AFTER (i.e. “post”) the values. Postfix Expression neverrequire the use of parentheses to express non-standard precedence.The fact that postfix expressions do not need parentheses makesthem much easier to evaluate than infix expressions. The conversionfrom an Infix Expression to a Postfix Expression can be done usinga stack.

A postfix expression is evaluated also using a stack. When avalue is encountered, it is pushed onto the stack. When an operatoris encountered, two values are popped from the stack. Those valuesare evaluated using the operation implies by the operator. Then theresult is pushed back onto the stack. When the end of a postfixexpression is encountered, the value on the top of the stack is theresult of the expression. There should only be one value on thestack when the end of the postfix expression is encountered.Examples of Postfix Expressions are:

42 64 +
60 43 18 * + 57 + 60 43 + 18 57 + * 18 12 – 3 –
18 12 3 – –

Both the algorithm to convert an infix expression to a postfixexpression and the algorithm to evaluate a postfix expressionrequire the use of stacks. Note that the conversion algorithmrequires a stack of operators, while the evaluation algorithmrequires a stack of values. Also note that the following algorithmmerges the conversion and evaluation algorithms into one, so itnever actually creates the Postfix Expression.

Algorithm for Infix Evaluation

First we will define the function popAndEval (OperatorStack,ValueStack ) as follows:

op = top (OperatorStack) pop (OperatorStack)
v2 = top (ValueStack) pop (ValueStack)

v1 = top (ValueStack) pop (ValueStack)
v3 = eval ( v1, op, v2 ) push (ValueStack, v3)

If you are trying to perform a top operation on an emptyValueStack, print out an error message and return the value of-999. If the operator op for eval () is not one of *, /, + or -,print out and error message and return the value of -999.

When getting the input for an infix expression, the programproj3base.c breaks everything down into “tokens”. There are 3 typesof tokens we are concerned with: an OPERATOR token, a VALUE tokenand the EndOfLine token. The code in the functionprocessExpression() already checks for these token but you willneed to add the code how to interact with the stacks.

First step, have both the OperatorStack and the ValueStackempty

While (the current token is not the EndOfLine Token) if ( thecurrent token is a VALUE )

push the value onto the ValueStack if ( the current token is anOPERATOR )

if ( the current operator is an Open Parenthesis )
push the Open Parenthesis onto the OperatorStack

if ( the current operator is + or - )
while ( the OperatorStack is not Empty &&

the top of the OperatorStack is +, -, * or / ) popAndEval (OperatorStack, ValueStack )

push the current operator on the OperatorStack if ( the currentoperator is * or / )

while ( the OperatorStack is not Empty && the top of theOperatorStack is * or / )

popAndEval ( OperatorStack, ValueStack ) push the currentoperator on the OperatorStack

if ( the current operator is a Closing Parenthesis ) while ( theOperator Stack is not Empty &&

the top of the OperatorStack is not an Open Parenthesis )popAndEval ( OperatorStack, ValueStack )

if (the OperatorStack is Empty ) print an error message

Program For Evaluation Of Postfix Expression Using Stack In Java

else
get the next token from the input

pop the Open Parenthesis from the OperatorStack

Once the EndOfLine token is encountered while (the OperatorStackis not Empty )

popAndEval ( OperatorStack, ValueStack )
Print out the top of the ValueStack at the result of the expressionPopping the ValueStack should make it empty, print error if notempty

The error statements in the above algorithm should only occur ifan invalid infix expression is given as input. You are not requiredto check for any other errors in the input.

Command Line Argument: Debug Mode

Your program is to be able to take one optional command lineargument, the -d flag. When this flag is given, your program is torun in 'debug' mode. When in this mode, your program should displaythe operators and values as they are encountered in the input. Theprintf statements for these are already included in the programproj3base.c, so you just have to “turn off” the printf statementswhen the –d flag is given.

When the flag is not given, this debugging information shouldnot be displayed. One simple way to set up a 'debugging' mode is touse a boolean variable which is set to true when debugging mode isturned on but false otherwise. This variable may be a globalvariable. Then using a simple if statement controls whetherinformation should be output or not.

if ( debugMode TRUE )
printf (' Debugging Information n');

Provided Code for the User Inteface

The code given in proj3base.c should properly provide for theuser interface for this program including all command errorchecking. This program has no code for the linked list. It is yourjob to write the functions for the specified operations and makethe appropriate calls. Most of the changes to the existing proj6.cprogram need to be made in the processExpression ( ) function. Lookfor the comments of:

Note: the heads of the linked list are required to be a localvariable in a function and you are required to pass the head of thelinked to the operation functions. The function processExpression()is strongly suggested as the functions in which to declared thelinked lists.