search
HomeJavajavaTutorialHow to implement postfix expression calculation in Java

中缀表示法java实现

观察一个普通的算式:3+4*5

我们当然知道,应该先计算 4*5 再将这个结果和3相加,就能得到最后的结果。

如果是一个复杂一些的算式:3+4*((5-6)/7+8)

这依然难不倒我们,只要牢记()的优先级最高,然后是*/,最后是+-就没问题了,这就是通常的中缀表示法。

但是通过算法分析,这样的表达式,由于每一次都需要判断优先级,所以运行的时间应当是O(N^2)。

在表达式很长很复杂的时候,就需要一种更适合计算机的算法来计算了。

后缀表示法

简介

逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。

逆波兰记法不需要括号来标识操作符的优先级。逆波兰记法中,操作符置于操作数的后面。

例如表达“三加四”时,写作“3 4 +”,而不是“3 +4”。如果有多个操作符,操作符置于第二个操作数的后面,所以常规中缀记法的“3 - 4 + 5”在逆波兰记法中写作“3 4 - 5+”:先3减去4,再加上5。——维基百科逆波兰表示法词条。

这种表示法有以下特点:

  • 不需要使用括号。和中缀表达式不同,逆波兰表达式不需要遍历整个算式来寻找一对括号。

  • 逆波兰表达式的实现一般基于堆栈。在计算机中,堆栈这种数据结构具有极快的效率。运行时间是O(N)。

  • 不满足交换律。

逆波兰表达式的计算方式

例如2*3+4*5

你可以这么计算,2 和 3 相乘的和是 5,把这个数存起来,再计算 4*5 的值,存起来, 最后在计算两个存在一起的值。写出来是这样子的 2 3 * 4 5 * + 。这就是后缀或逆波兰记法。

采用堆栈实现的过程很简单,规则如下。

从头开始读取。读取到如果是数字,则将其压入栈中。如果是一个符号,就取两次栈顶的元素通过该符号进行计算,再把得到的数压入栈中。

Java实现

public class PRNCalculator {    
       public static double PRNCal(String PRN){
              Stack<Double> stack = new Stack<Double>();
              String[] ss = PRN.split(" ");
              for(int i = 0; i < ss.length; i++){
                     if(ss[i].matches("\\d")) stack.push(Double.valueOf(ss[i]));
                     if(ss[i].matches("[+|-|*|/]")){
                           double b = stack.pop();
                           double a = stack.pop();
                           if(ss[i].equals("+")) stack.push(a + b);
                           if(ss[i].equals("-")) stack.push(a - b);
                           if(ss[i].equals("*")) stack.push(a * b);
                           if(ss[i].equals("/")) stack.push(a / b);
                     }
              }
              return stack.pop();
       }
}

Test类

public class PRNTest {
       public static void main(String[] args) {
              String s = "2 3 * 4 5 * + ";
              double result = PRNCalculator.PRNCal(s);
              System.out.println("输入的逆波兰表达式:" + s);
              System.out.println("计算结果:" + result);
       }
}

打印结果:

输入的逆波兰表达式:2 3 * 4 5 * +
计算结果:26.0

与中缀记法的转换

和后缀表达式的计算方法类似,一个中缀记法转换到后缀记法,也可以利用堆栈来实现。

从头开始读取。如果读取到的是数字,将其输出。如果读取到的是符号,则判断该符号的优先级是否高于栈顶或栈为空,是,则压入栈中;否,则将栈顶输出并继续判断。如果读取到的是括号,”(“会直接被压入栈;在读取到”)”的时候,栈会一直弹出直到遇到”(“。下面是这个转换的Java实现。

package PRNCalculator;
import java.util.Stack;
public class PRNCalculator {
       public static String PRNTansf(String s){
              Stack<String> stack = new Stack<String>();
              String[] ss = s.split(" ");
              StringBuffer sb = new StringBuffer();
              for(int i = 0; i < ss.length; i++){
                     if(ss[i].matches("\\d")) sb.append(ss[i] + " ");
                     if(ss[i].matches("[+|-|*|/|(|)]")) {
                           if(stack.isEmpty()) {
                                  stack.push(ss[i]);
                           } else {
                                  if(ss[i].matches("[+|-]")) {
                                         while(!stack.isEmpty() && !stack.peek().matches("[(]")) sb.append(stack.pop()).append(" ");
                                         if(stack.isEmpty() || stack.peek().matches("[(]")) stack.push(ss[i]);
                                  }
                                  if(ss[i].matches("[*|/]")){
                                         while(stack.peek().matches("[*|/]") && !stack.peek().matches("[(]")) sb.append(stack.pop()).append(" ");
                                         if(stack.isEmpty() || stack.peek().matches("[(]") || stack.peek().matches("[+|-]")) stack.push(ss[i]);
                                  }
                                  if(ss[i].matches("[(]")) {
                                         stack.push(ss[i]);
                                  }
                                  if(ss[i].matches("[)]")){
                                         while(!stack.peek().matches("[(]")) sb.append(stack.pop()).append(" ");
                                         if(stack.peek().matches("[(]")) stack.pop();
                                  }
                           }
                     }
              }
              while(!stack.isEmpty()) sb.append(stack.pop()).append(" ");
              return sb.toString();
       }
}
* Test类*

package PRNCalculator;
public class PRNTest {
       public static void main(String[] args) {
              String s = "4 + 5 + 8 * ( 6 + 8 * 7 ) / 3 + 4";
              String PRN = PRNCalculator.PRNTansf(s);
              System.out.println("输入的表达式为:");
              System.out.println(s);
              System.out.println("输出的逆波兰表达式为:");
              System.out.println(PRN);
              double result = PRNCalculator.PRNCal(PRN);
              System.out.println("该表达式计算结果为:");
              System.out.println(result);
       }
}

打印结果:

输入的表达式为:
4 + 5 + 8 * ( 6 + 8 * 7 ) / 3 + 4
输出的逆波兰表达式为:
4 5 + 8 6 8 7 * + * 3 / + 4 +
该表达式计算结果为:
178.33333333333334

java后缀表达式的计算

实现方法

从左至右扫描表达式

遇到数字时,将数字压栈,遇到运算符时,弹出栈顶的两个数,计算并将结果入栈

重复2直到表达式最右端,最后运算得出的值即为表达式的结果

示例

计算后缀表达式的值:1 2 3 + 4 × + 5 -

从左至右扫描,将1,2,3压入栈;

遇到+运算符,3和2弹出,计算2+3的值,得到5,将5压入栈;

遇到4,将4压入栈

遇到×运算符,弹出4和5,计算5×4的值,得到20,将20压入栈;

遇到+运算符,弹出20和1,计算1+20的值,得到21,将21压入栈;

遇到5,将5压入栈;

遇到-运算符,弹出5和21,计算21-5的值,得到16为最终结果

代码实现

public class ReversePolishNotation {

    public static void main(String[] args) {
        String notation = "10 2 3 + 4 * + 5 -";
        ReversePolishNotation reversePN = new ReversePolishNotation();
        Stack<Integer> numStack = new Stack<>();
        //以空格分隔上述表达式,存到数组中
        String[] s = notation.split(" ");
        //遍历数组
        for (int i = 0; i < s.length; i++) {
            if (!reversePN.isOperator(s[i])){
                //如果不是运算符,则压栈
                numStack.push(Integer.parseInt(s[i]));
            } else {
                //为运算符,则取出栈顶的两个数字进行运算
                int result = reversePN.calculation(numStack.pop(), numStack.pop(), s[i]);
                //将结果压栈
                numStack.push(result);
            }
        }
        //循环结束,栈中仅剩的一个元素及为结果
        System.out.println(numStack.pop());
    }
    //判断是否是运算符
    public boolean isOperator(String oper){
        return oper.equals("+") ||oper.equals("-")  ||oper.equals("*")  ||oper.equals("/") ;
    }
    //计算
    public int calculation(int num1, int num2, String oper){
        switch (oper){
            case "+":
                return num2 + num1;
            case "-":
                return num2 - num1;
            case "*":
                return num2 * num1;
            case "/":
                return num2 / num1;
            default:
                return 0;
        }
    }
}

The above is the detailed content of How to implement postfix expression calculation in Java. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:亿速云. If there is any infringement, please contact admin@php.cn delete
How do I use Maven or Gradle for advanced Java project management, build automation, and dependency resolution?How do I use Maven or Gradle for advanced Java project management, build automation, and dependency resolution?Mar 17, 2025 pm 05:46 PM

The article discusses using Maven and Gradle for Java project management, build automation, and dependency resolution, comparing their approaches and optimization strategies.

How do I create and use custom Java libraries (JAR files) with proper versioning and dependency management?How do I create and use custom Java libraries (JAR files) with proper versioning and dependency management?Mar 17, 2025 pm 05:45 PM

The article discusses creating and using custom Java libraries (JAR files) with proper versioning and dependency management, using tools like Maven and Gradle.

How do I implement multi-level caching in Java applications using libraries like Caffeine or Guava Cache?How do I implement multi-level caching in Java applications using libraries like Caffeine or Guava Cache?Mar 17, 2025 pm 05:44 PM

The article discusses implementing multi-level caching in Java using Caffeine and Guava Cache to enhance application performance. It covers setup, integration, and performance benefits, along with configuration and eviction policy management best pra

How can I use JPA (Java Persistence API) for object-relational mapping with advanced features like caching and lazy loading?How can I use JPA (Java Persistence API) for object-relational mapping with advanced features like caching and lazy loading?Mar 17, 2025 pm 05:43 PM

The article discusses using JPA for object-relational mapping with advanced features like caching and lazy loading. It covers setup, entity mapping, and best practices for optimizing performance while highlighting potential pitfalls.[159 characters]

How does Java's classloading mechanism work, including different classloaders and their delegation models?How does Java's classloading mechanism work, including different classloaders and their delegation models?Mar 17, 2025 pm 05:35 PM

Java's classloading involves loading, linking, and initializing classes using a hierarchical system with Bootstrap, Extension, and Application classloaders. The parent delegation model ensures core classes are loaded first, affecting custom class loa

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Chat Commands and How to Use Them
1 months agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

SublimeText3 Linux new version

SublimeText3 Linux new version

SublimeText3 Linux latest version