JAVA 1.Represent each of the following infix expressions as a postfix expression
ID: 3707875 • Letter: J
Question
JAVA
1.Represent each of the following infix expressions as a postfix expression:
a. (a+ b)/ (c- d)
b. a/(b-c)*d
c. a-(b/(c-d)*e+f)^g
d. (a-b*c)/(d*e^f*g+h)
2. Using the algorithm, evaluate each of the following postfix expressions.
Assume that a = 2, b = 3, c = 4, d = 5, and e = 6.
1. a e + b d - /
2. a b c * d * -
3. a b c - / d *
4. e b c a ^ * + d -
3. Implement the methods {Extra Credit 100 Points}
CheckBalance to check if an Infix expression is fully bracketed
Infix_to_Postfix to convert an Infix expression to Postfix Expression
Evaluate_Postfix to evaluate a postfix expression.
Explanation / Answer
Q1:
import java.util.Stack;
class Test
{
static int Prec(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
static String infixToPostfix(String exp)
{
// initializing empty String for result
String result = new String("");
Stack<Character> stack = new Stack<>();
for (int i = 0; i<exp.length(); ++i)
{
char c = exp.charAt(i);
if (Character.isLetterOrDigit(c))
result += c;
else if (c == '(')
stack.push(c);
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);
}
}
while (!stack.isEmpty())
result += stack.pop();
return result;
}
// Driver method
public static void main(String[] args)
{
String exp1 = "(a+b)/(c-d)";
String exp2 = "a/(b-c)*d";
String exp3 = "a-(b/(c-d)*e+f)^g";
String exp4 = "(a-b*c)/(d*e^f*g+h)";
System.out.println("a) "+infixToPostfix(exp1));
System.out.println("b) "+infixToPostfix(exp2));
System.out.println("c) "+infixToPostfix(exp3));
System.out.println("d) "+infixToPostfix(exp4));
}
}
answer:
2) Following is tha java code:
import java.util.Stack;
public class Test
{
static int evaluatePostfix(String exp)
{
Stack<Integer> stack=new Stack<>();
for(int i=0;i<exp.length();i++)
{
char c=exp.charAt(i);
if(Character.isDigit(c))
stack.push(c - '0');
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)
{
String exp1="26+35-/";
String exp2="234*5*-";
String exp3="234-/5*";
String exp4="6342^*+5-";
System.out.println("1) "+evaluatePostfix(exp1));
System.out.println("2) "+evaluatePostfix(exp2));
System.out.println("3) "+evaluatePostfix(exp3));
System.out.println("4) "+evaluatePostfix(exp4));
}
}
answer:
3) Check Parentheses:
public class BalancedParan
{
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;
}
}
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;
}
static boolean areParenthesisBalanced(char exp[])
{
stack st=new stack();
for(int i=0;i<exp.length;i++)
{
if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
st.push(exp[i]);
if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
{
if (st.isEmpty())
{
return false;
}
else if ( !isMatchingPair(st.pop(), exp[i]) )
{
return false;
}
}
}
if (st.isEmpty())
return true; /*balanced*/
else
{ /*not balanced*/
return false;
}
}
public static void main(String[] args)
{
char exp[] = {'{','(',')','}','[',']'};
if (areParenthesisBalanced(exp))
System.out.println("Balanced ");
else
System.out.println("Not Balanced ");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.