写一个中缀表前缀的java程序
时间: 2024-02-13 14:06:49 浏览: 20
中缀表达式转前缀表达式可以使用栈来实现,可以按照以下步骤进行:
1. 初始化一个栈和一个结果字符串。
2. 将中缀表达式翻转,得到反转后的表达式。
3. 遍历反转后的表达式中的每个字符。
4. 如果当前字符是数字或字母,则将其添加到结果字符串中。
5. 如果当前字符是右括号")",则将其压入栈中。
6. 如果当前字符是左括号"(",则将栈中所有的右括号依次弹出并添加到结果字符串中,直到遇到右括号为止,然后将右括号弹出。
7. 如果当前字符是运算符,比如"+","-","*","/"等,则将栈中所有优先级大于该运算符的右括号和运算符依次弹出并添加到结果字符串中,然后将该运算符压入栈中。
8. 遍历完反转后的表达式后,如果栈中还有右括号或运算符,则将它们依次弹出并添加到结果字符串中。
9. 将结果字符串再次翻转即可得到前缀表达式。
下面是Java代码实现:
```java
import java.util.Stack;
public class InfixToPrefix {
public static String infixToPrefix(String infix) {
Stack<Character> stack = new Stack<>();
StringBuilder prefix = new StringBuilder();
String reversed = new StringBuilder(infix).reverse().toString();
for (int i = 0; i < reversed.length(); i++) {
char c = reversed.charAt(i);
if (Character.isLetterOrDigit(c)) {
prefix.append(c);
} else if (c == ')') {
stack.push(c);
} else if (c == '(') {
while (!stack.isEmpty() && stack.peek() != ')') {
prefix.append(stack.pop());
}
stack.pop();
} else {
while (!stack.isEmpty() && precedence(c) < precedence(stack.peek())) {
prefix.append(stack.pop());
}
stack.push(c);
}
}
while (!stack.isEmpty()) {
prefix.append(stack.pop());
}
return prefix.reverse().toString();
}
public static int precedence(char c) {
switch (c) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return -1;
}
}
public static void main(String[] args) {
String infix = "a+b*(c^d-e)^(f+g*h)-i";
String prefix = infixToPrefix(infix);
System.out.println(prefix); // 输出:-+a^bc*^-d+efgh*i
}
}
```
在上面的代码中,我们使用了一个优先级函数`precedence`来判断运算符的优先级,根据不同的运算符返回不同的优先级值。在主函数中,我们输入了一个中缀表达式,然后调用`infixToPrefix`函数将其转换为前缀表达式,最后输出前缀表达式。