我正在编写一个从中缀到后缀的程序(使用堆栈)，但经过所有这些努力，有些地方出了问题。我得到的输出是没有转换的中缀，请检查我的intopost方法是否正确。
//stack class also containing the intopostfix method
import java.util.*;
public class Stack
{ int i,j;
char postfix[];
char stack[];
int top;
String post;
public Stack(int n)
{
stack=new char[n];
top=-1;
}
public void push(char item)
{
if(top>=stack.length)
System.out.println("Stack overflow");
else
{
stack[++top]=item;
}
}
public char pop()
{
if(top==-1)
{ System.out.println("Stack underflow");
return 0;
}
else
return stack[top--];
}
boolean isAlpha(char ch)
{
if((ch>='a'&&ch<='z')||(ch>=0&&ch<='9'))
return true;
else
return false;
}
boolean isOperator(char ch)
{
if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
return true;
else return false;
}
void intopost(String str)
{
postfix=new char[str.length()];
char ch;
j=0;
for(i=0;i<str.length();i++)
{
ch=str.charAt(i);
if(ch=='(')
push(ch);
else if(isAlpha(ch))
{
postfix[j++]=ch;
}
else if(isOperator(ch))
{
push (ch);
}
else if(ch==')')
{
while((pop())!='(')
{
postfix[j++]=pop();
}
}
}
}
void disp()
{
for(i=0;i<postfix.length;i++)
{
System.out.print(postfix[i]);
}
}
}
首先更改以下行
if((ch>='a'&&ch<='z')||(ch>=0&&ch<='9'))
进入
if((ch>='a'&&ch<='z')||(ch>='0' &&ch<='9'))
然后
else if(ch==')')
{
while((pop())!='(')
{
postfix[j++]=pop();
}
}
在这里，您调用了两次pop函数。这会导致堆栈下溢。应该调用一次。
最后尝试以下
void intopost(String str)
{
postfix=new char[str.length()];
char ch;
j=0;
for(i=0;i<str.length();i++)
{
ch=str.charAt(i);
if(ch=='(')
push(ch);
else if(isAlpha(ch))
{
postfix[j++]=ch;
}
else if(isOperator(ch))
{
push (ch);
}
else if(ch==')')
{
char c = pop();
while(c!='(')
{
postfix[j++]=c;
c= pop();
}
}
}
}
以下程序将为您完成
import java.io.*;
class stack
{
char stack1[]=new char[20];
int top;
void push(char ch)
{
top++;
stack1[top]=ch;
}
char pop()
{
char ch;
ch=stack1[top];
top--;
return ch;
}
int pre(char ch)
{
switch(ch)
{
case '-':return 1;
case '+':return 1;
case '*':return 2;
case '/':return 2;
}
return 0;
}
boolean operator(char ch)
{
if(ch=='/'||ch=='*'||ch=='+'||ch=='-')
return true;
else
return false;
}
boolean isAlpha(char ch)
{
if(ch>='a'&&ch<='z'||ch>='0'&&ch=='9')
return true;
else
return false;
}
void postfix(String str)
{
char output[]=new char[str.length()];
char ch;
int p=0,i;
for(i=0;i<str.length();i++)
{
ch=str.charAt(i);
if(ch=='(')
{
push(ch);
}
else if(isAlpha(ch))
{
output[p++]=ch;
}
else if(operator(ch))
{
if(stack1[top]==0||(pre(ch)>pre(stack1[top]))||stack1[top]=='(')
{
push(ch);
}
}
else if(pre(ch)<=pre(stack1[top]))
{
output[p++]=pop();
push(ch);
}
else if(ch=='(')
{
while((ch=pop())!='(')
{
output[p++]=ch;
}
}
}
while(top!=0)
{
output[p++]=pop();
}
for(int j=0;j<str.length();j++)
{
System.out.print(output[j]);
}
}
}
class intopost
{
public static void main(String[] args)throws Exception
{
String s;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
stack b=new stack();
System.out.println("Enter input string");
s=br.readLine();
System.out.println("Input String:"+s);
System.out.println("Output String:");
b.postfix(s);
}
}
Output:
Enter input string
a+b*c
Input String:a+b*c
Output String:
abc*+
Enter input string
a+(b*c)/d
Input String:a+(b*c)/d
Output String:
abc*d/)(+
公共类InfixToPostfix{私有堆栈；private字符串中缀；private字符串输出="；public InfixToPostfix(字符串输入){infix=输入；stack=新堆栈(infix.length())；}public字符串convertInfixToPostfix(){for(int index=0；index<infix.length()；索引++){char itemRead=中缀.charAt(索引)；开关(项目读取){大小写'+'：大小写"-"：processOperator(itemRead，1)；打破案例'*'：案例'/'：processOperator(itemRead，2)；打破案例"("：stack.prush(itemRead)；打破案例")"：popStackTillOpen圆括号()；打破默认值：output=output+itemRead；打破}}while(！stack.isEmpty()){output=output+stack.op()；}返回输出；}public void processOperator(char infixOperator，int优先级)｛while(！stack.isEmpty()){char popedOpr=stack.pop()；if(popedOpr=='('){stack.prush(popedOpr)；打破}其他的{int popedOpr递减；if(popedOpr=='+'||popedOpr=='-')popedOpr递减=1；其他的popedOpr递减=2；if(popedOprPredence<优先级)｛stack.prush(popedOpr)；打破}其他的输出=输出+popedOpr；}}stack.prush(infixOperator)；}public void popStackTillOpenParenthesis()｛while(！stack.isEmpty()){char popedOpr=stack.pop()；if(popedOpr=='(')打破其他的输出=输出+popedOpr；}}}
后缀表示法的解释、算法和示例如下：http://www.thinkscholar.com/java/java-topics/infix-to-postfix/http://www.thinkscholar.com/java/java-topics/infix-to-postfix/
试试这个代码
/**
* Checks if the input is operator or not
* @param c input to be checked
* @return true if operator
*/
private boolean isOperator(char c){
if(c == '+' || c == '-' || c == '*' || c =='/' || c == '^')
return true;
return false;
}
/**
* Checks if c2 has same or higher precedence than c1
* @param c1 first operator
* @param c2 second operator
* @return true if c2 has same or higher precedence
*/
private boolean checkPrecedence(char c1, char c2){
if((c2 == '+' || c2 == '-') && (c1 == '+' || c1 == '-'))
return true;
else if((c2 == '*' || c2 == '/') && (c1 == '+' || c1 == '-' || c1 == '*' || c1 == '/'))
return true;
else if((c2 == '^') && (c1 == '+' || c1 == '-' || c1 == '*' || c1 == '/'))
return true;
else
return false;
}
/**
* Converts infix expression to postfix
* @param infix infix expression to be converted
* @return postfix expression
*/
public String convert(String infix){
String postfix = ""; //equivalent postfix is empty initially
Stack<Character> s = new Stack<>(); //stack to hold symbols
s.push('#'); //symbol to denote end of stack
for(int i = 0; i < infix.length(); i++){
char inputSymbol = infix.charAt(i); //symbol to be processed
if(isOperator(inputSymbol)){ //if a operator
//repeatedly pops if stack top has same or higher precedence
while(checkPrecedence(inputSymbol, s.peek()))
postfix += s.pop();
s.push(inputSymbol);
}
else if(inputSymbol == '(')
s.push(inputSymbol); //push if left parenthesis
else if(inputSymbol == ')'){
//repeatedly pops if right parenthesis until left parenthesis is found
while(s.peek() != '(')
postfix += s.pop();
s.pop();
}
else
postfix += inputSymbol;
}
//pops all elements of stack left
while(s.peek() != '#'){
postfix += s.pop();
}
return postfix;
}
这是从我的博客上截取的。访问以获取完整的代码，并详细查看转换的每个步骤。还要注意，这里还考虑了括号和指数，它们可以转换任何表达式。
试试这段代码，效率更高，因为这里我没有使用很多方法，只是使用主方法。
package inn;
导入com.sun.org.apache.bcel.internal.generic.GTO；导入java.util.Scanner；
/****@作者MADMEN*/
公共类Half_Life｛
public Half_Life()
{
// a+b*c
// a*b+c
// d/e*c+2
// d/e*(c+2)
// (a+b)*(c-d)
// (a+b-c)*d/f
// (a+b)*c-(d-e)^(f+g)
// (4+8)*(6-5)/((3-2)*(2+2))
//(300+23)*(43-21)/(84+7) -> 300 23+43 21-*84 7+/
}
public static void main(String[] args)
{
System.out.print("n Enter Expression : ");
Scanner c=new Scanner(System.in);
String exp=c.next();
int sym_top=0,po_top=-1,p=0,p2=0;
int size=exp.length();
char a[]=exp.toCharArray();
char symbols[]=new char[size];
char pfix[]=new char[size];
symbols[sym_top]='$';
for(int i=0;i<size;i++)
{
char c1=a[i];
if(c1==')')
{
while(sym_top!=0)
{
if(symbols[sym_top]=='(')
break;
pfix[++po_top]=symbols[sym_top--];
}
sym_top--;
}
else if(c1=='(')
{
symbols[++sym_top]=c1;
}
else if(c1=='+' || c1=='-' || c1=='*' || c1=='/' || c1=='^')
{
switch(c1)
{
case '+':
case '-': p=2;
break;
case '*':
case '/': p=4;
break;
case '^': p=5;
break;
default: p=0;
}
if(sym_top<1)
{
symbols[++sym_top]=c1;
}
else
{
do
{
char c2=symbols[sym_top];
if(c2=='^')
{
p2=5;
}
else if(c2=='*' || c2=='/')
{
p2=4;
}
else if(c2=='+' || c2=='-')
{
p2=2;
}
else
{
p2=1;
}
if(p2>=p)
{
pfix[++po_top]=symbols[sym_top--];
}
if(p>p2 || symbols[sym_top]=='$')
{
symbols[++sym_top]=c1;
break;
}
}while(sym_top!=-1);
}
}
else
{
pfix[++po_top]=c1;
}
}
for(;sym_top>0;sym_top--)
{
pfix[++po_top]=symbols[sym_top];
}
System.out.print("n Infix to Postfix expression : ");
for(int j=0;j<=po_top;j++)
{
System.out.print(pfix[j]);
}
System.out.println("n");
}
}
检查最后一个大括号。
您可以在以下网址索取更多数据结构程序：sankie2902@gmail.com