EVALUATING GENERAL INFIX EXPRESSIONS
INTRODUCTION
The notation in which we usually write arithmetic expressions is
called infix notation; in it, operators are
written between their operands: X + Y. Such
expressions can be ambiguous; do we add or multiply first in the
expression 5 + 3 * 2? Parentheses and rules of precedence and
association clarify such ambiguities: multiplication and division
take precedence over addition and subtraction, and operators
associate from left to right.
This project implements and exercises a stack-based algorithm that
evaluates infix expressions according to the conventional rules of
precedence and association.
DESCRIPTION
Design, implement, document, and test a program that reads infix
expressions from a file, one expression per line. The
program echoes the expressions, evaluates them using the
stack-based algorithm described in class, and reports their
values.
INPUT
The program reads the name of a file, then from the file reads
syntactically correct general infix expressions
involving single-digit integers and binary
arithmetic operators: +, -, *, and /.
OUTPUTThe program prompts for the input file name and prints to the
terminal each expression in the file and its value.
ERRORSThe program can assume that its input is as described; it
need not detect any errors.
EXAMPLE
If a data file infix.dat is this: 5 + 7 * (9 -
6) + 3 8 + 4 / 2 (8 + 4) / 2 (6 + (7 - 3)) * ((9 / 3) + 2) * 4 then
a run of the program might look like this: Enter input file name:
infix.dat Expression: 5 + 7 * ( 9 - 6 ) + 3 Value = 29. Expression:
8 + 4 / 2 Value = 10. Expression: ( 8 + 4 ) / 2 Value = 6.
Expression: ( 6 + ( 7 - 3 ) ) * ( ( 9 / 3 ) + 2 ) * 4 Value =
200.
OTHER REQUIREMENTS
Implement a stack abstract data type in
a class. Use
the sequential (array-based) stack
implementation.
HINTS
The program will use two stacks, one of integers (for
operands) and one of characters (for operators), so it
will #include two stack classes that
differ only in the types of object in their stacks.
Operands will be single digits; this greatly simplifies input and
allows us to concentrate on the evaluation algorithm and its
interaction with the stacks. (If you wrote a multi-digit integer
function for a previous project, you can use it here if you
like.)
Consider a function called, say, apply(optr, opnd1,
opnd2) that returns the value that results when the
operator optr is applied to the two operands
that are the function's second and third parameters.
written in C++
#include<iostream>
#include<fstream>
using namespace std;
//OPERAND STACK
class node
{
public:
int data;
node* next;
};
class OperandStack
{
public:
OperandStack(int max)
{
top = NULL;
capacity = max;
length=0;
}
void push(int val)
{
if(length == capacity)
cout<<"Full Stack"<<endl;
else
{
node *newTop = new node;
if(top == NULL)
{
newTop->data = val;
newTop->next = NULL;
top = newTop;
length++;
}
else
{
newTop->data = val;
newTop->next = top;
top = newTop;
length++;
}
}
}
int pop()
{
if(top == NULL)
cout<< "Empty Stack"<<endl;
else
{
node * old = top;
int val = old->data;
top = top->next;
length--;
delete(old);
return val;
}
}
int peek()
{
if(top == NULL)
cout<< "Empty Stack"<<endl;
else
{
node * old = top;
int val = old->data;
return val;
}
}
bool empty()
{
if(top == NULL)
return true;
else
return false;
}
void print()
{
node *temp;
temp = top;
while(temp!=NULL)
{
cout<<temp->data<<",";
temp=temp->next;
}
}
private:
node *top;
int length;
int capacity;
int stackData;
};
//OPERATOR STACK
class opnode
{
public:
char data;
opnode* next;
};
class OperatorStack
{
public:
OperatorStack(int max)
{
top = NULL;
capacity = max;
length=0;
}
void push(char val)
{
if(length == capacity)
cout<<"Full Stack"<<endl;
else
{
opnode *newTop = new opnode;
if(top == NULL)
{
newTop->data = val;
newTop->next = NULL;
top = newTop;
length++;
}
else
{
newTop->data = val;
newTop->next = top;
top = newTop;
length++;
}
}
}
char pop()
{
if(top == NULL)
cout<< "Empty Stack"<<endl;
else
{
opnode * old = top;
char c = old->data;
top = top->next;
length--;
delete(old);
return c;
}
}
char peek()
{
if(top == NULL)
cout<< "Empty Stack"<<endl;
else
{
opnode * old = top;
char c = old->data;
return c;
}
}
bool empty()
{
if(top == NULL)
return true;
else
return false;
}
void print()
{
opnode *temp;
temp = top;
while(temp!=NULL)
{
cout<<temp->data<<",";
temp=temp->next;
}
}
private:
opnode *top;
int length; //head
int capacity;
char stackData;
};
// precedence FINDER
int precedence(char optr){
if(optr == '+'||optr == '-')
return 1;
if(optr == '*'||optr == '/')
return 2;
return 0;
}
// Function to perform arithmetic operations.
int apply(int opnd1, int opnd2, char optr){
switch(optr){
case '+': return opnd1 + opnd2;
case '-': return opnd1 - opnd2;
case '*': return opnd1 * opnd2;
case '/': return opnd1 / opnd2;
}
}
// function to evaluate infix expression
int evaluate(string expression){
int i;
// stack to hold integers
OperandStack *operandStack = new OperandStack(500);
// stack to hold operators.
OperatorStack *operatorStack = new OperatorStack(500);
for(i = 0; i < expression.length(); i++){
//skip spaces
if(expression[i] == ' ')
continue;
// push open brace as it is
else if(expression[i] == '('){
operatorStack->push(expression[i]);
}
//if its a number push it to operandStack
else if(isdigit(expression[i])){
int val = 0;
//check if that number has multiple digits
while(i < expression.length() &&
isdigit(expression[i]))
{
val = (val*10) + (expression[i]-'0');
i++;
}
operandStack->push(val);
}
//solve the entire expression within, if a closing brace is found
else if(expression[i] == ')')
{
while(!operatorStack->empty() && operatorStack->peek() != '(')
{
int val2 = operandStack->peek();
operandStack->pop();
int val1 = operandStack->peek();
operandStack->pop();
char op = operatorStack->peek();
operatorStack->pop();
operandStack->push(apply(val1, val2, op));
}
//pop opening brace
operatorStack->pop();
}
//if +, -, * or / has come then
else
{
//check precedence and act accordingly
while(!operatorStack->empty() && precedence(operatorStack->peek())
>= precedence(expression[i])){
int val2 = operandStack->peek();
operandStack->pop();
int val1 = operandStack->peek();
operandStack->pop();
char op = operatorStack->peek();
operatorStack->pop();
operandStack->push(apply(val1, val2, op));
}
//push present operator to operatorStack
operatorStack->push(expression[i]);
}
}
//finally, evaluate all the remaining operators in the OperatorStack
while(!operatorStack->empty()){
int val2 = operandStack->peek();
operandStack->pop();
int val1 = operandStack->peek();
operandStack->pop();
char op = operatorStack->peek();
operatorStack->pop();
operandStack->push(apply(val1, val2, op));
}
//return the top element of OperandStack as result
return operandStack->peek();
}
//MAIN FUNCTION
int main() {
string filename,expression;
cout<<"Enter input file name: ";
cin>>filename;
//reading the file line by line
ifstream f (filename);
if (!f.is_open())
perror("error while opening file");
while(getline(f, expression)) {
cout<<endl<<endl<<" Expression: "<<expression<<endl;
//calling the evaluate function for each expression in a line
cout << evaluate(expression) << "\n";
}
//EXTRA LINE TO CHECK THIS SOLUTION IF NEEDED WITHOUT INPUTTING FILE
// cout<<endl<<evaluate(" ( 6 + ( 7 - 3 ) ) ( ( 9 / 3 ) + 2 ) 4")<<endl;
return 0;
}
EVALUATING GENERAL INFIX EXPRESSIONS INTRODUCTION The notation in which we usually write arithmetic expressions is called infix notation;...
Stacks are used by compilers to help in the process of evaluating expressions and generating machine language code.In this exercise, we investigate how compilers evaluate arithmetic expressions consisting only of constants, operators and parentheses. Humans generally write expressions like 3 + 4and 7 / 9in 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...
We as humans write math expression in infix notation, e.g. 5 + 2 (the operators are written in-between the operands). In a computer’s language, however, it is preferred to have the operators on the right side of the operands, i.e. 5 2 +. For more complex expressions that include parenthesis and multiple operators, a compiler has to convert the expression into postfix first and then evaluate the resulting postfix. Write a program that takes an “infix” expression as input, uses...
Total point: 15 Introduction: For this assignment you have to write a c program that will take an infix expression as input and display the postfix expression of the input. After converting the postfix expression, the program should evaluate the expression from the postfix and display the result. What should you submit? Write all the code in a single file and upload the .c file. Problem We as humans write math expression in infix notation, e.g. 5 + 2 (the...
Write a java program for the following: Your program reads an infix expression represented by a string S from the standard input (the keyboard). Then your program converts the infix expression into a postfix expression P using the algorithm. Next, your program evaluates the postfix expression P to produce a single result R. At last, your program displays the original infix expression S, the corresponding postfix expression P and the final result R on the standard output ( the screen...
In C programming Language Write a version of the infix-to-postfix conversion algorithm. Write a program that converts an ordinary infix arithmetic expression (assume a valid expression is entered) with single-digit integers For Example: Infix expression (6 + 2) * 5 - 8 / 4 to a postfix expression is 62+5*84/- The program should read the expression into character array infix and use the stack functions implemented in this chapter to help create the postfix expression in character array postfix. The...
Using Java- Write a program that takes an arithmetic expression in an infix form, converts it to a postfix form and then evaluates it. Use linked lists for the infix and postfix queues and the operator and value stacks. You must use sperate Stack and Queue classes with a driver class to run the program. example Input : 111++ Output : (1+ (1+ 1)) Answer: 3
In c++ Section 1. Stack ADT – Overview Data Items The data items in a stack are of generic DataType. This means use should use templating and your Node class. Structure The stack data items are linearly ordered from the most recently added (the top) to the least recently added (the bottom). This is a LIFO scheme. Data items are inserted onto (pushed) and removed from (popped) the top of the stack. Operations Constructor. Creates an empty stack. Copy constructor....
Write a C++ program that reads string expressions from an input file "prefix.txt" containing prefix expressions (one expression per input line). For each prefix expression read from the input file, the program should: (1) convert the expression to a fully parenthesized infix expression and (2) find the value of the expression. Use a stack to solve the problem. Assume the expressions contain only integer numbers and the *,/, +, - operators. Generate the results in an output file "results.txt" in...
You are to write a program name expressionTree.java that evaluates an infix expression entered by the user. The expression may contain the following tokens: (1) Integer constants (a series of decimal digits). (2) One alphabetic character - "x" (representing a value to be supplied later). (3) Binary operators (+, -, *, / and % (modulo)). (4) Parentheses You will parse the input expression creating an expression tree with the tokens, then use the postOrder tree traversal algorithm to extract...
Infix Expression Evaluator For this project, write a C program that will evaluate an infix expression. The algorithm REQUIRED for this program will use two stacks, an operator stack and a value stack. Both stacks MUST be implemented using a linked list. For this program, you are to write functions for the linked list stacks with the following names: int isEmpty (stack); void push (stack, data); data top (stack); void pop (stack); // return TRUE if the stack has no...