This question is for \" Data Structure course \". ( check the image below ) I pr

Question

This question is for "Data Structure course". (check the image below)

I prefer a brief answer & If you are going to use any programming language to solve this problem, then use JAVA language.

** Please don't provide a handwritten solution or a picture of the solution. Just post the answer here so I can read it easily.

Expression: a * - b + c

Problem 4 Write the postfix form of the infix expression below. Then describe how each token is processed to generate postfix expression out by using stack expression a b c

Explanation / Answer

import java.io.IOException;
public class InfixToPostfix {
private Stack stack;
private String inp;
private String opt = "";
public InfixToPostfix(String in) {
inp = in;
int stackSize = inp.length();
stack = new Stack(stackSize);
}
public String scan() {
for (int j = 0; j < inp.length(); j++) {
char ch = inp.charAt(j);
switch (ch) {
case '+':
case '-':
getOpr(ch, 1);
break;
case '*':
case '/':
getOpr(ch, 2);
break;
case '(':
theStack.push(ch);
break;
case ')':
getParent(ch);
break;
default:
opt = opt + ch;
break;
}
}
while (!stack.isEmpty()) {
opt = opt + stack.pop();
}
System.out.println(opt);
return opt;
}
public void getOpr(char opThis, int prec1) {
while (!stack.isEmpty()) {
char opTop = stack.pop();
if (opTop == '(') {
stack.push(opTop);
break;
} else {
int prec2;
if (opTop == '+' || opTop == '-')
prec2 = 1;
else
prec2 = 2;
if (prec2 < prec1) {
stack.push(opTop);
break;
}
else opt = opt + opTop;
}
}
stack.push(opThis);
}
public void getParent(char ch) {
while (!stack.isEmpty()) {
char chx = stack.pop();
if (chx == '(')
break;
else opt = opt + chx;
}
}
public static void main(String[] args) throws IOException {
String inp = "a*-b+c";
String opt;
InfixToPostfix doScan = new InfixToPostfix(inp);
opt = doScan.scan();
System.out.println("Postfix is " + opt + ' ');
}

class Stack {
private int max;
private char[] sArr;
private int top;
  
public Stack(int max) {
max = max;
sArr = new char[max];
top = -1;
}
public void push(char j) {
sArr[++top] = j;
}
public char pop() {
return sArr[top--];
}
public char peek() {
return sArr[top];
}
public boolean isEmpty() {
return (top == -1);
}
}
}

Description :

In the scan method each character is verified in a switch case .

If it is a normal alphabet it is added to output postfix expression

Else if it is + or *or/ , the getOperator method is called which takes precedence as parameter .

It compares that if precedence of top in stack is greater than current operator then it pops the top operator to the output expression and pushes current to top ,in the else case it pushes current operator on to the top of stack. if the character scanned is a closing bracket then the getParent method it pops all characters until the next opening bracket into the output expression.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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