The concept of stack is extremely important in computer science and is used in a

Question

The concept of stack is extremely important in computer science and is used in a wide variety of problems. This assignment requires you to write a program that can be used to evaluate ordinary arithmetic expressions that contains any of the five arithmetic operators (+, -, *, /, %).

This exercise requires three distinct steps, namely:-

Verify that the infix arithmetic expression (the original expression), that may contain regular parentheses, is properly formed as far as parentheses are concerned.

If the parenthesized expression is properly formed, convert the expression from an infix expression to its equivalent postfix expression, called Reverse Polish Notation (RPN) named after the Polish Mathematician J. Lukasiewics.

Evaluate the postfix expression, and print the result.

Step 1 - Verify that the expression

Given an arithmetic expression, called an infixed expression, to verify that it is properly formed as far as parentheses are concerned, do the following:

Create an empty stack to hold left parenthesis ONLY.

Scanned the arithmetic expression is from left to right, one character at a time.

While the are more characters in the arithmetic expression

{

If the character is a left parenthesis ‘(‘, push it on to the stack. However if the character is a right parenthesis, ‘)’, visit the stack and pop the top element from off the stack.

}

If the stack contains any element at the end of reading the arithmetic expression, then the expression was not properly formed.

Step 2 - Convert infixed expression to postfix

Given that an arithmetic expression is properly form with respect to parentheses, do the following:

Create an empty stack to hold any arithmetic operators and left parenthesis, ONLY.

A string variable to contain the postfix expression (i.e., the output from this conversion).

Scan the arithmetic expression from left to right.

While there are more symbols in the arithmetic expression,

{

After a symbol is scanned, there are four (4) basic rules to observe and apply accordingly:

If the symbol is an operand (i.e., a number), write it to the output string.

If the symbol is an operator and if the stack is empty, push the symbol on the stack.

Otherwise, if the symbol is either ‘(‘ or ‘)’, check for the following conditions:

If the symbol is ‘(‘, push on to the stack,

         Otherwise

If the symbol is ‘)’

{

         Pop everything from the operator stack down to the first ‘(‘. Write each item

popped from the stack to the output string. Do not write either of the parentheses onto the output string. Discard them.

}

If the symbol scanned is an arithmetic operator, check for the following and apply accordingly:

If the operator on the top of the stack has higher or equal precedence than the one that was currently read, pop that operator from off the stack, and write it to the output string. This process continues until one of two things happen:

Either the first ‘(‘ is encountered. When this occurs, the ‘(‘ is removed from the stack and is discarded, and the recently scanned symbol is placed on the stack

OR

Push the recently scanned symbol onto the stack.

}

4. When the arithmetic expression is exhausted, any operator is remaining on the stack must be popped from off and is written to the output string.

Step 3 - Evaluate the post fixed expression

Initialize an empty stack that will store operands only.

Scan the postfix string one token (i.e., numbers) at a time.

While there are more tokens in the postfix string

{

If the token is an operand, push it onto the stack.

If the token is an operator

{

Pop the two topmost values from the stack, and store them in the order t1, the topmost, and t2 the second value.

Calculate the partial result in the following order t2 operator t1

Push the result of this calculation onto the stack.

NOTE: If the stack does not have two operands, a malformed postfix expression has occurred, and evaluation should be terminated.

}

}

When the end of the input string is encountered, the result of the expression is popped from the stack.

NOTE: If the stack is empty or if it has more than one operand remaining, the result is unreliable.

Extend this algorithm to include square brackets and curly braces. For example, expressions of the following kind should be considered:

2 + { 2 * ( 10 – 4 ) / [ { 4 * 2 / ( 3 + 4) } + 2 ] – 9 }

2 + } 2 * ( 10 – 4 ) / [ { 4 * 2 / ( 3 + 4) } + 2 ] – 9 {

Only the following are considered valid nestings:

( )

{ }

[ ]

{ ( ) }

[ ( ) ]

[ { } ]

[ { ( ) } ]

Implement the above two algorithms for the following binary operators: addition +, subtraction -, multiplication *, division /, and modulus operation %. All operations are integer operations. To keep things simple, place at least one blank space between each token in the input string.

Here's what I was given from my teacher

-1 Arithmetic class

-Another arithmetic class defining the "isBalance" method.

-Test class

.I just need to fill in some methods, but I do need to turn it in with this format. Please help.

Explanation / Answer

import java.util.Stack;

public class Arithmetic
{
  
static class stack
{
int top=-1;
char items[] = new char[100];

void push(char x)
{
if (top == 99)
{
System.out.println("Stack full");
}
else
{
items[++top] = x;
}
}

char pop()
{
if (top == -1)
{
System.out.println("Underflow error");
return '';
}
else
{
char element = items[top];
top--;
return element;
}
}

boolean isEmpty()
{
return (top == -1) ? true : false;
}
}

/* Returns true if character1 and character2
are matching left and right Parenthesis */
static boolean isMatchingPair(char character1, char character2)
{
if (character1 == '(' && character2 == ')')
return true;
else if (character1 == '{' && character2 == '}')
return true;
else if (character1 == '[' && character2 == ']')
return true;
else
return false;
}

/* Return true if expression has balanced
Parenthesis */
static boolean areParenthesisBalanced(char exp[])
{
/* Declare an empty character stack */
stack st=new stack();
  
/* Traverse the given expression to
check matching parenthesis */
for(int i=0;i<exp.length;i++)
{

/*If the exp[i] is a starting
parenthesis then push it*/
if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
st.push(exp[i]);
  
/* If exp[i] is an ending parenthesis
then pop from stack and check if the
popped parenthesis is a matching pair*/
if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
{
  
/* If we see an ending parenthesis without
a pair then return false*/
if (st.isEmpty())
{
return false;
}
  
/* Pop the top element from stack, if
it is not a pair parenthesis of character
then there is a mismatch. This happens for
expressions like {(}) */
else if ( !isMatchingPair(st.pop(), exp[i]) )
{
return false;
}
}

}

/* If there is something left in expression
then there is a starting parenthesis without
a closing parenthesis */

if (st.isEmpty())
return true; /*balanced*/
else
{ /*not balanced*/
return false;
}
}
  
static int Prec(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
  
case '*':
case '/':
return 2;
  
case '^':
return 3;
}
return -1;
}
  
// The main method that converts given infix expression
// to postfix expression.
static String infixToPostfix(String exp)
{
// initializing empty String for result
String result = new String("");

// initializing empty stack
Stack<Character> stack = new Stack<>();

for (int i = 0; i<exp.length(); ++i)
{
char c = exp.charAt(i);

// If the scanned character is an operand, add it to output.
if (Character.isLetterOrDigit(c))
result += c;
  
// If the scanned character is an '(', push it to the stack.
else if (c == '(')
stack.push(c);

// If the scanned character is an ')', pop and output from the stack
// until an '(' is encountered.
else if (c == ')')
{
while (!stack.isEmpty() && stack.peek() != '(')
result += stack.pop();

if (!stack.isEmpty() && stack.peek() != '(')
return "Invalid Expression"; // invalid expression   
else
stack.pop();
}
else // an operator is encountered
{
while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek()))
result += stack.pop();
stack.push(c);
}
  
}
  
// pop all the operators from the stack
while (!stack.isEmpty())
result += stack.pop();
  
return result;
}

// Method to evaluate value of a postfix expression
static int evaluatePostfix(String exp)
{
//create a stack
Stack<Integer> stack=new Stack<>();

// Scan all characters one by one
for(int i=0;i<exp.length();i++)
{
char c=exp.charAt(i);

// If the scanned character is an operand (number here),
// push it to the stack.
if(Character.isDigit(c))
stack.push(c - '0');

// If the scanned character is an operator, pop two
// elements from stack apply the operator
else
{
int val1 = stack.pop();
int val2 = stack.pop();

switch(c)
{
case '+':
stack.push(val2+val1);
break;

case '-':
stack.push(val2- val1);
break;

case '/':
stack.push(val2/val1);
break;

case '*':
stack.push(val2*val1);
break;
}
}
}
return stack.pop();   
}
  
public static void main(String[] args)
{
char exp[] = {'{','(',')','}','[',']'};
if (areParenthesisBalanced(exp))
System.out.println("Balanced ");
else
System.out.println("Not Balanced ");
  
String exp2 = "a+b*(c^d-e)^(f+g*h)-i";
System.out.println("The post fixed expression is " +infixToPostfix(exp2));
  
String exp1="231*+9-";
System.out.println(evaluatePostfix(exp1));
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.