THE ZEPINT NETWORK

programmer assist

Java Java XML Feeds

Java Questions Java Solutions Java Articles

Java is an object-oriented programming language developed initially by James Gosling and colleagues at Sun Microsystems. The language, initially called Oak (named after the oak trees outside Gosling's office), was intended to replace C++, although the feature set better resembles that of Objective C. Java should not be confused with JavaScript, which shares only the name and a similar C-like syntax. Sun Microsystems currently maintains and updates Java regularly.

infix to postfix, infix to prefix

DiggBlinkRedditDeliciousTechnorati

question by abel | Moderate

The conversion from infix to postfix expression and infix to prefix expression

Post reply Subscriptions

Re: infix to postfix, infix to prefix

answer by Srirangan

Converts infix arithmetic expressions to postfix

import java.io.IOException;

public class InToPost {
private Stack theStack;

private String input;

private String output = "";

public InToPost(String in) {
input = in;
int stackSize = input.length();
theStack = new Stack(stackSize);
}

public String doTrans() {
for (int j = 0; j < input.length(); j++) {
char ch = input.charAt(j);
switch (ch) {
case '+':
case '-':
gotOper(ch, 1);
break; // (precedence 1)
case '*': // it's * or /
case '/':
gotOper(ch, 2); // go pop operators
break; // (precedence 2)
case '(': // it's a left paren
theStack.push(ch); // push it
break;
case ')': // it's a right paren
gotParen(ch); // go pop operators
break;
default: // must be an operand
output = output + ch; // write it to output
break;
}
}
while (!theStack.isEmpty()) {
output = output + theStack.pop();

}
System.out.println(output);
return output; // return postfix
}

public void gotOper(char opThis, int prec1) {
while (!theStack.isEmpty()) {
char opTop = theStack.pop();
if (opTop == '(') {
theStack.push(opTop);
break;
}// it's an operator
else {// precedence of new op
int prec2;
if (opTop == '+' || opTop == '-')
prec2 = 1;
else
prec2 = 2;
if (prec2 < prec1) // if prec of new op less
{ // than prec of old
theStack.push(opTop); // save newly-popped op
break;
} else
// prec of new not less
output = output + opTop; // than prec of old
}
}
theStack.push(opThis);
}

public void gotParen(char ch){
while (!theStack.isEmpty()) {
char chx = theStack.pop();
if (chx == '(')
break;
else
output = output + chx;
}
}

public static void main(String[] args) throws IOException {
String input = "1+2*4/5-7+3/6";
String output;
InToPost theTrans = new InToPost(input);
output = theTrans.doTrans();
System.out.println("Postfix is " + output + '
');

}
class Stack {
private int maxSize;

private char[] stackArray;

private int top;

public Stack(int max) {
maxSize = max;
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);
}
}

}

Post reply Subscriptions

Re: infix to postfix, infix to prefix

reply by sammy

can u give me a simplier java program in converting infix to prefix

Post reply Subscriptions

Re: infix to postfix, infix to prefix

reply by Adisa

Hi everyone!
I have a question related to this problem. My programming problem is that the user will have to input an infix expression. Then the program converts the expression from infix to postfix. After that, the program will evaluate the program by line according to the order of operation. Here is the sample output:
User input: 2 + 3 * 2 ^ 3
Output evaluation:
2 + 3 * 8
2 + 24
26

My sample code generates the result but it doesn't output the expression line by line. It just generate the final result. It doesn't also accept exponents. The only operators it accepts are +, -, * / and %. But it can recognize parenthesis. Can you please help me? Here is my sample code.
import java.io.*;
import java.util.*;

public class ExpressionEvaluator
{
// initialize two stacks: operator and operand
private static Stack operatorStack = new Stack();
private static Stack operandStack = new Stack();

// method converts infix expression to postfix notation
private static String toPostfix(String infix)
{
StringTokenizer s = new StringTokenizer(infix);
// divides the input into tokens for input
String symbol, postfix = "";
while (s.hasMoreTokens())
// while there is input to be read
{
symbol = s.nextToken();
// if it's a number, add it to the string
if (Character.isDigit(symbol.charAt(0)))
postfix = postfix + " " + (Integer.parseInt(symbol));
else if (symbol.equals("("))
// push "("
{
Character operator = new Character('(');
operatorStack.push(operator);
}
else if (symbol.equals(")"))
// push everything back to "("
{
while (((Character)operatorStack.peek()).charValue() != '(')
{
postfix = postfix + " " + operatorStack.pop();
}
operatorStack.pop();
}
else
// print operatorStack occurring before it that have greater precedence
{
while (!operatorStack.empty() && !(operatorStack.peek()).equals("(") && prec(symbol.charAt(0)) <= prec(((Character)operatorStack.peek()).charValue()))
postfix = postfix + " " + operatorStack.pop();
Character operator = new Character(symbol.charAt(0));
operatorStack.push(operator);
}
}
while (!operatorStack.empty())
postfix = postfix + " " + operatorStack.pop();
return postfix;
}

// method evaulates postfix expression
private static int evaluate(String postfix)
{
StringTokenizer s = new StringTokenizer(postfix);
// divides the input into tokens for input
int value;
String symbol;
while (s.hasMoreTokens())
{
symbol = s.nextToken();
if (Character.isDigit(symbol.charAt(0)))
// if it's a number, push it onto stack
{
Integer operand = new Integer(Integer.parseInt(symbol));
operandStack.push(operand);
}
else // if it's an operator, operate on the previous two popped operandStack items
{
int op2 = ((Integer)operandStack.pop()).intValue();
int op1 = ((Integer)operandStack.pop()).intValue();
int result = 0;
switch(symbol.charAt(0))
{
case '*': {result = op1 * op2; break;}
case '+': {result = op1 + op2; break;}
case '-': {result = op1 - op2; break;}
case '/': {result = op1 / op2; break;}
case '%': {result = op1 % op2; break;}
case '^': {result = op1 ^ op2; break;}
}
Integer operand = new Integer(result);
operandStack.push(operand);
}
}
value = ((Integer)operandStack.pop()).intValue();
return value;
}

// method compares operators to establish precedence
private static int prec(char x)
{
if (x == '+' || x == '-')
{
return 1;
}
else if (x=='^' && x == '*' || x == '/' || x == '%')
{
return 2;
}
else
{
return 0;
}
}

// main method
public static void main(String argv[]) throws IOException
{
String infix;

// inputs stream for string of characters
BufferedReader keyboard = new BufferedReader (new InputStreamReader(System.in));

// inputs expression in infix notation
System.out.print("Expression in infix: ");
infix = keyboard.readLine();

// displays postfix notation
System.out.println("Expression in postfix:" + toPostfix(infix));

// displays evaluated expression
System.out.println("Evaluated expression: " + evaluate(toPostfix(infix)));
}
}
Please reply ASAP.
Thank you.
Adisa

Post reply Subscriptions

Got a Java Question?

Just Sign Up and ask the top Java experts!

Search via Google

User Login

Email Address

Password

Java Experts

Rank Expert Points
#1 Srirangan 100
This a list of the Top Java experts, how many points do you have?

Leading Experts

Rank Expert Points
#1 frankzzsword 4650
#2 Bejaan 2950
#3 csfreak 1100
#4 Anurag 700
#5 keyvez 700
#6 nnarasimha 600
#7 Nakata 600
#8 martinig 600
#9 mastercomputers 550
#10 Abhishek Chatterjee 250
#11 Abels 250
#12 Huntress 150
#13 Adkron 150
#14 Yogesh 100
#15 lexxwern 100
This is a list of overall best performing experts, how many points do you have?