Infix to Postfix Java

2025年5月2日 | 8 分钟阅读

中缀和后缀表达式可以包含以下运算符：'+', '-', '%','*', '/' 以及从 a 到 z 的字母。运算符 (+, -) 的优先级低于运算符 (*, /, %) 的优先级。括号具有最高优先级，其中的表达式必须首先被转换。在本节中，我们将学习如何通过 Java 程序将中缀表达式转换为后缀表达式以及后缀表达式转换为中缀表达式。

为了进行转换，我们使用堆栈数据结构。堆栈用于存储运算符和括号，以强制执行优先级。从左到右开始解析表达式。在继续本节之前，请确保您熟悉堆栈及其操作。让我们看看中缀和后缀表达式。

中缀表达式

中缀表达式是指运算符写在两个或多个操作数之间的表达式。通常，我们使用中缀表达式。例如，考虑以下表达式。

a+b
a/2+c*d-e*(f*g)
a*(b+c)/d

后缀表达式

后缀表达式是指运算符写在其操作数之后的表达式。例如，考虑以下表达式。

ab+
abc/de+*+f-
ab+cd-*

中缀与后缀表达式对比

中缀表达式	后缀表达式
A*B/C	AB*C/
(A/(B-C+D))(E-A)C	ABC-D+/EA-C
A/B-C+DE-AC	AB/C-DEAC-

中缀转后缀转换示例

将(X - Y / (Z + U) * V) 中缀表达式转换为后缀表达式。

序号	输入	操作数堆栈	后缀表达式
1	(	(	-
2	X	(	X
3	-	( -	X
4	Y	( -	XY
5	/	( - /	XY
6	(	( - / (	XY
7	Z	( - / (	XYZ
8	+	( - / ( +	XYZ
9	U	( - / ( +	XYZU
10	)	( - /	XYZU+
11	*	( - *	XYZU+/
12	V	( - *	XYZU+/V
13	)	-	XYZU+/V*-

算法

从左到右逐个字符扫描中缀表示式。
如果扫描到的下一个符号是操作数，则将其附加到后缀字符串。
如果扫描到的下一个符号是运算符，则
1. 从堆栈中弹出并附加到后缀字符串的所有运算符，这些运算符
  1. 位于最近扫描到的左括号之上，并且
  2. 具有高于或等于新运算符符号的优先级（对于右结合运算符）。
2. 将新运算符推入堆栈。
如果扫描到左括号，则将其推入堆栈。
如果扫描到右括号，则必须将所有运算符弹出直到最近扫描到的左括号，并附加到后缀字符串。此外，必须丢弃一对括号。
当完全扫描完中缀字符串后，堆栈中可能仍然包含一些运算符。所有剩余的运算符都应被弹出并附加到后缀字符串。

让我们在 Java 程序中实现上述算法。

Java 程序将中缀表达式转换为后缀表达式

InfixToPostfixConversion.java

import java.io.*;
class Stack
{
char a[]=new char[100];
int top=-1;
void push(char c)
{
try
{
a[++top]= c;
}
catch(StringIndexOutOfBoundsException e)
{
System.out.println("Stack full, no room to push, size=100");
System.exit(0);
}
}
char pop()
{
return a[top--];
}
boolean isEmpty()
{
return (top==-1)?true:false;
}
char peek()
{
return a[top];
}
}	
public class InfixToPostfix
{
static Stack operators = new Stack();		
public static void main(String argv[]) throws IOException
{
String infix;
//create an input stream object
BufferedReader keyboard = new BufferedReader (new InputStreamReader(System.in));
//get input from user
System.out.print("\nEnter the infix expression you want to convert: ");
infix = keyboard.readLine();
//output as postfix
System.out.println("Postfix expression for the given infix expression is:" + toPostfix(infix));
}
private static String toPostfix(String infix)
//converts an infix expression to postfix
{
char symbol;
String postfix = "";
for(int i=0;i<infix.length();++i)
//while there is input to be read
{
symbol = infix.charAt(i);
//if it's an operand, add it to the string
if (Character.isLetter(symbol))
postfix = postfix + symbol;
else if (symbol=='(')
//push (
{
operators.push(symbol);
}
else if (symbol==')')
//push everything back to (
{
while (operators.peek() != '(')
{
postfix = postfix + operators.pop();
}
operators.pop();		//remove '('
}
else
//print operators occurring before it that have greater precedence
{
while (!operators.isEmpty() && !(operators.peek()=='(') && prec(symbol) <= prec(operators.peek()))
postfix = postfix + operators.pop();
operators.push(symbol);
}
}
while (!operators.isEmpty())
postfix = postfix + operators.pop();
return postfix;
}
static int prec(char x)
{
if (x == '+' || x == '-')
return 1;
if (x == '*' || x == '/' || x == '%')
return 2;
return 0;
}
}

输出

解释

此 Java 代码使用堆栈数据结构将中缀表达式转换为后缀表达式。它使用一个堆栈类来实现基本的堆栈操作，如 push、pop、isEmpty() 和 peek。为了转换中缀表达式为后缀表达式，主类 InfixToPostfix 首先要求用户提交表达式，然后调用 toPostfix() 方法。

toPostfix() 方法处理中缀表达式中的每个字符。左括号被压入堆栈，而操作数（字母）被直接插入到后缀字符串中。当遇到右括号时，运算符从堆栈中弹出并添加到后缀字符串，直到遇到相应的左括号为止。

后缀转中缀转换示例

将AB + CD - / 后缀表达式转换为中缀表达式。

序号	输入	操作数堆栈	中缀表达式
1	A	A	-
2	B	A, B	-
3	+	A + B	A + B
4	C	A + B, C	A + B - C
5	D	A + B, C, D	A + B - C
6	-	A + B, C - D	A + B - C - D
7	/	A + B / C - D	A + B / C - D

算法

从左到右逐个字符读取后缀表达式。
如果它是操作数，则推入操作数堆栈。
如果它是运算符，则
1. 从堆栈中弹出两个操作数。
2. 从中缀表达式中弹出，然后推入操作数堆栈。
如果表达式未结束，则转到第一步。
弹出操作数堆栈并显示。
退出

让我们在 Java 程序中实现上述算法。

Java 程序将后缀表达式转换为中缀表达式

PostfixToInfixConversion.java

import java.util.Scanner;
import java.util.Stack;
public class PostfixToInfixConversion
{
//user-defined function that checks the character is operator or not    
private boolean isOperator(char ch) 
{
if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^')
//returns true if either of the operator is found
return true;
//else returns false
return false;
}
//user-defined function that performs conversion
public String convertPostfixToInfix(String postfixstring) 
{
//implementing stack    
Stack<String> s = new Stack<>();
//iterates over the postfix expression
for (int i = 0; i < postfixstring.length(); i++) 
{
//reading a character at a time    
char ch = postfixstring.charAt(i);
//inside the if-statement we have called the user-defined function that checks whether the character is operator or not
if (isOperator(ch)) 
{
String b = s.pop();
String a = s.pop();
//push the character (operator) into stack in between the string a and b
s.push("(" + a + ch + b + ")");
} 
else
//push character into the stack
s.push("" + ch);
}
//pop character from the stack and returns the same
return s.pop();
}
public static void main(String args[]) 
{
//creating object of the class
PostfixToInfixConversion obj = new PostfixToInfixConversion();
Scanner sc = new Scanner(System.in);
System.out.print("Enter the postfix expression you want to convert: ");
//reads a postfix expression from the user
String postfixstring = sc.next(); //for example ab+
//prints the infix expression
System.out.println("Infix expression for the given postfix expression is: " + obj.convertPostfixToInfix(postfixstring));
}
}

输出

解释

此 Java 代码使用堆栈数据结构将后缀表达式转换为中缀表达式。isOperator() 方法检查一个字符是否为运算符。在 convertPostfixToInfix() 方法中，堆栈用于存储操作数和中间中缀表达式。

它遍历后缀表达式的每个字符。如果遇到运算符，它会从堆栈中弹出两个操作数，将它们与括号括起来的运算符连接起来，然后将生成的字符串推回堆栈。如果字符是操作数，它只会将其推入堆栈。最后，返回堆栈顶部的元素，该元素代表中缀表达式。

main() 方法创建一个 PostfixToInfixConversion 类的对象，提示用户输入后缀表达式，调用转换方法，并打印生成的中缀表达式。

评估后缀表达式

后缀表达式在评估时特别方便，因为它们消除了对括号和显式运算符优先级规则的需求。以下是评估后缀表达式的算法：

扫描后缀表达式：从左到右开始扫描后缀表达式。
遇到操作数：如果遇到操作数，则将其推入操作数堆栈。
遇到运算符：如果遇到运算符，则从操作数堆栈中弹出前两个元素（作为运算符的操作数），执行运算，然后将结果推回操作数堆栈。
重复直到结束：重复步骤 2 和 3，直到后缀表达式结束。
最终结果：处理完整个表达式后，最终结果将是操作数堆栈中唯一剩余的元素。

让我们在 Java 中实现后缀表达式的评估。

PostfixEvaluation.java

import java.util.*;
public class PostfixEvaluation {
    public static int evaluatePostfix(String postfix) {
        Stack<Integer> stack = new Stack<>();
        for (char c : postfix.toCharArray()) {
            if (Character.isDigit(c)) {
                stack.push(c - '0'); // Convert character digit to integer
            } else {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                switch(c) {
                    case '+':
                        stack.push(operand1 + operand2);
                        break;
                    case '-':
                        stack.push(operand1 - operand2);
                        break;
                    case '*':
                        stack.push(operand1 * operand2);
                        break;
                    case '/':
                        stack.push(operand1 / operand2);
                        break;
                    case '%':
                        stack.push(operand1 % operand2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    public static void main(String[] args) {
        String postfixExpression = "23*5+"; // Example postfix expression
        int result = evaluatePostfix(postfixExpression);
        System.out.println("Result of evaluating postfix expression: " + result);
    }
}

输出

Result of evaluating postfix expression: 11

解释

在此程序中，运算符处理部分对于评估后缀表达式至关重要。遇到运算符时，会从堆栈中弹出顶部的两个操作数。这些操作数代表表达式中的右操作数和左操作数。然后，根据遇到的运算符，程序会在两个操作数之间执行相应的算术运算。结果随后被推回堆栈。

例如，当程序遇到 '*' 运算符时，它会弹出顶部的两个操作数，将它们相乘，然后将结果推回堆栈。类似地，对于 '+'、'-'、'/' 和 '%' 等其他运算符，程序会执行相应的算术运算。

在遍历完整个后缀表达式并评估所有运算符和操作数后，最终结果是堆栈中唯一剩余的元素，然后将其弹出并作为后缀表达式评估的结果返回。这种方法利用堆栈数据结构和算术运算，提供了一种高效且系统的方法来评估后缀表达式。

结论

总而言之，了解中缀和后缀表达式以及如何转换它们对于计算机科学和编程至关重要，尤其是在解析和表达式评估等任务中。本文涵盖了中缀和后缀表达式的概念、它们的区别以及将中缀表达式转换为后缀表达式以及反之亦然的技术。对于这两种转换过程，我们还包含了详细的描述和 Java 实现。

下一主题Java 中的实例变量隐藏

Infix to Postfix Java

中缀表达式

后缀表达式

中缀与后缀表达式对比

中缀转后缀转换示例

算法

Java 程序将中缀表达式转换为后缀表达式

后缀转中缀转换示例

算法

Java 程序将后缀表达式转换为中缀表达式

评估后缀表达式

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Infix to Postfix Java

中缀表达式

后缀表达式

中缀与后缀表达式对比

中缀转后缀转换示例

算法

Java 程序将中缀表达式转换为后缀表达式

后缀转中缀转换示例

算法

Java 程序将后缀表达式转换为中缀表达式

评估后缀表达式

结论

相关帖子

Association in Java

Getter and Setter Method in Java Example

Java 中 ChoiceFormat parse() 方法及示例

Java Color Codes

Java 中的 Stream mapToDouble() 方法及示例

How to Improve Coding Skills in Java

Java 中的菱形图案

在 Java 中创建自定义泛型类

URLify a Given String (Replace spaces with %20) in Java

Java Code for DES

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器