Mengubah Ekspresi Infix menjadi Postfix

Ekspresi Infix merupakan ekspresi yang digunakan jika operator (tanda +, -, *, /, ^) berada ditengah-tengah operand/variabel yang ingin dihitung. Ekspresi Infix merupakan ekspresi yang paling sering kita gunakan sehari-hari. Contoh ekspresi infix, yaitu :

1. a+b*c/d
2. (a^b)*c-d    

Berbeda dengan ekspresi infix, ekspresi postfix menuliskan operator setelah operand yang dimaksud telah dituliskan, misalnya kita akan menambahkan 'a' dengan 'b', kemudian kita mengalikan 'e' dengan 'd' baru mengurangi hasil setelahnya. Contoh berikut akan menunjukkan perbedaan ekspresi infix dan postfix.

    

    Ekspresi Infix     : a+b-(e*d)

    Ekspresi Postfix : ab+ed*-

1. Stack

	import java.io.IOException;
	import java.util.Scanner;
	class Main {
	public static void main(String[] args) throws IOException{
	String input, output;
	while(true){
	System.out.print("Enter infix: ");
	Scanner scanner = new Scanner(System.in);
	input = scanner.nextLine();
	if( input.equals(""))
	break;
	ToPostfix theTrans = new ToPostfix(input);
	output = theTrans.trabslation();
	System.out.println("Postfix is " + output + '\n');
	}
	}
	}

view raw Main hosted with ❤ by GitHub

	public class Queue {
	private int size;
	char queueArr[];
	int front;
	int rear;
	int currentSize = 0;
	public Queue(int size) {
	this.size = size;
	front = 0;
	rear = -1;
	queueArr = new char[this.size];
	}
	public void enqueue(char data) {
	if (!isFull()){
	rear++;
	if (rear == size) {
	rear = 0;
	}
	queueArr[rear] = data;
	currentSize++;
	}
	}
	public char dequeue() {
	char fr = 0;
	if (!isEmpty()){
	fr = queueArr[front];
	front++;
	if (front == size) {
	front = 0;
	}
	currentSize--;
	return fr;
	}
	return fr;
	}
	public boolean isFull() {
	if (currentSize == size) {
	return true;
	}
	return false;
	}
	public boolean isEmpty() {
	if (currentSize == 0) {
	return true;
	}
	return false;
	}
	public String getString(){
	String str = "";
	while(!isEmpty()){
	str = str + dequeue();
	}
	return str;
	}
	}

view raw Queue hosted with ❤ by GitHub

	class Stack
	{
	private int maxSize;
	private char[] stackArray;
	private int top;
	public Stack(int s){
	maxSize = s;
	stackArray = new char[maxSize];
	top = -1;
	}
	public void push(char j){
	stackArray[++top] = j;
	}
	public char pop(){
	return stackArray[top--];
	}
	public char peek(){
	return stackArray[top];
	}
	public boolean isEmpty(){
	return (top == -1);
	}
	public int size(){
	return top+1;
	}
	public char peekN(int n){
	return stackArray[n];
	}
	}

view raw Stack hosted with ❤ by GitHub

	lass ToPostfix{
	private Stack theStack;
	private String input;
	private Queue queue;
	public ToPostfix(String in){
	input = in;
	int stackSize = input.length();
	int queueSize = input.length();
	queue = new Queue(queueSize);
	theStack = new Stack(stackSize);
	}
	public String trabslation(){
	for(int j=0; j<input.length(); j++)
	{
	char ch = input.charAt(j);
	switch(ch)
	{
	case '+':
	case '-':
	operand(ch, 1);
	break;
	case '*':
	case '/':
	operand(ch, 2);
	break;
	case '(':
	theStack.push(ch);
	break;
	case ')':
	parent(ch);
	break;
	default:
	queue.enqueue(ch);
	break;
	}
	}
	while( !theStack.isEmpty()){
	queue.enqueue(theStack.pop());
	}
	return queue.getString();
	}
	public void operand(char opThis, int prec1){
	while( !theStack.isEmpty()){
	char opTop = theStack.pop();
	if( opTop == '(' ){
	theStack.push(opTop);
	break;
	}else{
	int prec2;
	if(opTop=='+' || opTop=='-')
	prec2 = 1;
	else
	prec2 = 2;
	if(prec2 < prec1){
	theStack.push(opTop);
	break;
	}
	else
	queue.enqueue(opTop);
	}
	}
	theStack.push(opThis);
	}
	public void parent(char ch){
	while( !theStack.isEmpty()){
	char chx = theStack.pop();
	if( chx == '(' )
	break;
	else
	queue.enqueue(chx);
	}
	}
	}

view raw ToPostfix hosted with ❤ by GitHub

2. Queue

	public class Queue {
	private int size;
	char queueArr[];
	int front;
	int rear;
	int currentSize = 0;
	public Queue(int size) {
	this.size = size;
	front = 0;
	rear = -1;
	queueArr = new char[this.size];
	}
	public void enqueue(char data) {
	if (!isFull()){
	rear++;
	if (rear == size) {
	rear = 0;
	}
	queueArr[rear] = data;
	currentSize++;
	}
	}
	public char dequeue() {
	char fr = 0;
	if (!isEmpty()){
	fr = queueArr[front];
	front++;
	if (front == size) {
	front = 0;
	}
	currentSize--;
	return fr;
	}
	return fr;
	}
	public boolean isFull() {
	if (currentSize == size) {
	return true;
	}
	return false;
	}
	public boolean isEmpty() {
	if (currentSize == 0) {
	return true;
	}
	return false;
	}
	public String getString(){
	String str = "";
	while(!isEmpty()){
	str = str + dequeue();
	}
	return str;
	}
	}

view raw Queue hosted with ❤ by GitHub

3. ToPostfix

	class ToPostfix{
	private Stack theStack;
	private String input;
	private Queue queue;
	public ToPostfix(String in){
	input = in;
	int stackSize = input.length();
	int queueSize = input.length();
	queue = new Queue(queueSize);
	theStack = new Stack(stackSize);
	}
	public String trabslation(){
	for(int j=0; j<input.length(); j++)
	{
	char ch = input.charAt(j);
	switch(ch)
	{
	case '+':
	case '-':
	operand(ch, 1);
	break;
	case '*':
	case '/':
	operand(ch, 2);
	break;
	case '(':
	theStack.push(ch);
	break;
	case ')':
	parent(ch);
	break;
	default:
	queue.enqueue(ch);
	break;
	}
	}
	while( !theStack.isEmpty()){
	queue.enqueue(theStack.pop());
	}
	return queue.getString();
	}
	public void operand(char opThis, int prec1){
	while( !theStack.isEmpty()){
	char opTop = theStack.pop();
	if( opTop == '(' ){
	theStack.push(opTop);
	break;
	}else{
	int prec2;
	if(opTop=='+' || opTop=='-')
	prec2 = 1;
	else
	prec2 = 2;
	if(prec2 < prec1){
	theStack.push(opTop);
	break;
	}
	else
	queue.enqueue(opTop);
	}
	}
	theStack.push(opThis);
	}
	public void parent(char ch){
	while( !theStack.isEmpty()){
	char chx = theStack.pop();
	if( chx == '(' )
	break;
	else
	queue.enqueue(chx);
	}
	}
	}

view raw ToPostfix hosted with ❤ by GitHub

4. Main

	import java.io.IOException;
	import java.util.Scanner;
	class Main {
	public static void main(String[] args) throws IOException{
	String input, output;
	while(true){
	System.out.print("Enter infix: ");
	Scanner scanner = new Scanner(System.in);
	input = scanner.nextLine();
	if( input.equals(""))
	break;
	ToPostfix theTrans = new ToPostfix(input);
	output = theTrans.trabslation();
	System.out.println("Postfix is " + output + '\n');
	}
	}
	}

view raw Main hosted with ❤ by GitHub

Output

Bagikan Artikel ini