Re: infix to postfix, infix to prefixanswer 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 prefixreply by sammy can u give me a simplier java program in converting infix to prefix
Post reply
Subscriptions
Re: infix to postfix, infix to prefixreply 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!
|