Tugas 21 April 2021

 Mengubah Ekspresi INFIX to POSTFIX Menggunakan Stack dan Queue

Pengertian

• Ekspresi infix merupakan notasi yang terbentuk atas operator dengan operand, dimana operator berada diantara operand. Notasi ini hanya dikenal oleh manusia dan selalu digunakan dalam perhitungan aritmatika.
  

           Contoh :  A + B * C
                          ( A + B ) * C
                           A – ( B + C ) * D ^ E

• Ekspresi postfix yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada dibelakang operand. Notasi ini hanya dikenal oleh processor dan dipahami dalam ALU. 

           Contoh :  A + B * C (Infix)
           maka notasi postfixnya adalah   ABC*+

Beberapa Program yang Digunakan :

Stack Class

	public class Stack implements StackInterface {
	ArrayList<Character> stack = new ArrayList<Character>();
	public void push(char ch) {
	stack.add(ch);
	}
	public char top() {
	char myCh;
	myCh = stack.get(stack.size() - 1);
	return myCh;
	}
	public char pop() {
	char myCh;
	myCh = stack.get(stack.size() - 1);
	stack.remove(stack.get(stack.size() - 1));
	return myCh;
	}
	public boolean ismt() {
	boolean retval = true;
	retval = stack.isEmpty();
	return retval;
	}
	}

view raw Stack hosted with ❤ by GitHub

Queue Class

	public class Queue implements QueueInterface {
	ArrayList<Character> que = new ArrayList<Character>();
	@Override
	public void add2Rear(char ch) { // add element to rear of queue
	que.add(ch);
	}
	@Override
	public char removeFront() { // returns first element AND removes it
	char retval = '1';
	retval = que.remove(0);
	return retval;
	}
	@Override
	public char front() { // returns first element
	char retval = '1';
	retval = que.get(0);
	return retval;
	}
	@Override
	public boolean ismtQ() { // true: if empty, false: if otherwise
	boolean retval = true;
	retval = que.isEmpty();
	return retval;
	}
	}

view raw Queue hosted with ❤ by GitHub

Infix to Postfix

	import java.util.Stack;
	public class InfixToPostFix {
	static int precedence(char c){
	switch (c){
	case '+':
	case '-':
	return 1;
	case '*':
	case '/':
	return 2;
	case '^':
	return 3;
	}
	return -1;
	}
	static String infixToPostFix(String expression){
	String result = "";
	Stack<Character> stack = new Stack<>();
	for (int i = 0; i <expression.length() ; i++) {
	char c = expression.charAt(i);
	//check if char is operator
	if(precedence(c)>0){
	while(stack.isEmpty()==false && precedence(stack.peek())>=precedence(c)){
	result += stack.pop();
	}
	stack.push(c);
	}else if(c==')'){
	char x = stack.pop();
	while(x!='('){
	result += x;
	x = stack.pop();
	}
	}else if(c=='('){
	stack.push(c);
	}else{
	//character is neither operator nor (
	result += c;
	}
	}
	for (int i = 0; i <=stack.size() ; i++) {
	result += stack.pop();
	}
	return result;
	}
	public static void main(String[] args) {
	String exp = "A+B*(C^D-E)";
	System.out.println("Infix Expression: " + exp);
	System.out.println("Postfix Expression: " + infixToPostFix(exp));
	}
	}

view raw Infix hosted with ❤ by GitHub

Output: