专栏首页给永远比拿愉快计算器:中缀表达式转后缀表达式

计算器:中缀表达式转后缀表达式

这几天想写一个Android的计算器,所以先写好中缀表达式到后缀表达式的计算。

例如:中缀表达式(8+9*10)-4/2+3 我们可以进行如下操作: 1、将每个操作符对应的两个操作数用括号括上(((8+(9*10))-(4/2))+3) 2、将操作符移到对应的括号外(((8(910*)+)(42)/)-3)+ 3、去掉括号即可  8910*+42/-3+

是不是很简单,这样我们就讲一个中缀表达式转换成论文后缀表达式。

那么计算机中是怎样进行的呢? 转换的整体流程如下: 中缀表达式转后缀表达式的方法: 1.遇到操作数:直接输出(添加到后缀表达式中) 2.栈为空时,遇到运算符,直接入栈 3.遇到左括号:将其入栈 4.遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出。 5.遇到其他运算符:加减乘除:弹出所有优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈 6.最终将栈中的元素依次出栈,输出。

下面是我写得一个示例代码:

package cn.tzy.calculator;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

/**
 * Created by gchx on 2015/2/9.
 */
public class Calculator {
	
    private Map<String, Integer> priority;//操作符优先级Map

    public Calculator() {
        initPriority();
    }

    private void initPriority() {
        this.priority = new HashMap<>();
        //这里的#号是操作符堆栈中的栈底元素,是为了程序方便处理而添加的
        this.priority.put("#", 0);
        this.priority.put("+", 1);
        this.priority.put("-", 1);
        this.priority.put("*", 2);
        this.priority.put("/", 2);
    }

    //得到操作符的优先级
    public int getPriority(String operator) {
        //这里括号进行特殊处理
        if (operator.matches("[()]")) {
            return -1;
        } else {
            return priority.get(operator);
        }
    }
   
    //判断优先级高低
    private boolean isPrior(String one, String another) {
        return getPriority(one) <= getPriority(another);
    }

    //得到栈顶元素
    private <T> T getTopEle(Stack<T> stack) {
        if (stack == null) {
            return null;
        } else {
            return stack.get(stack.size() - 1);
        }
    }

    /**
     * @param expression 算数表达式
     * @return
     * 将中缀表达式转换为后缀表达式
     */
    public Queue<String> toSuffix(String expression) {
    	Queue<String> operandQueue = new LinkedList<>();//操作数队列
        Stack<String> operatorStack = new Stack<>();//操作符堆栈
        operatorStack.push("#");

        String current = "";
        String operator = "";
        String number = "";
        int start = 0;
        int end = 0;
        for (int i = 0; i < expression.length(); i++) {
            current = String.valueOf(expression.charAt(i));
            // 如果是数字,末尾标记end++
            if (current.matches("[\\d\\.]")) {
                // 如果数字是最后一个字符,直接将其入队列
                if (i == expression.length() - 1) {
                    operandQueue.add(current);
                } else {
                    end++;
                }
            } else {
                // 如果是字符
                // 如果是左括号,将其入栈
                if (current.equals("(")) {
                    operatorStack.push(current);
                } else {
                    // 如果是右括号和其它运算符,先将前面的数字入队列
                    number = expression.substring(start, end);
                    if (!number.isEmpty()) {
                    	operandQueue.add(number);
					}
                    // 如果是右括号,执行出栈操作,并将出栈的元素入队列,直到弹出栈的是左括号,左括号直接出栈
                    if (current.equals(")")) {
                        while (!getTopEle(operatorStack).equals("(")) {
                            operandQueue.add(operatorStack.pop());
                        }
                        operatorStack.pop();
                    } else {
                        // 如果是其它运算符,弹出所有优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈
                        operator = current;
                        while (isPrior(operator, getTopEle(operatorStack))) {
                            operandQueue.add(operatorStack.pop());
                        }
                        operatorStack.push(operator);
                    }
                }
                // 将指向数字的首尾指针加1
                start = end = i + 1;
            }
        }

        for (int i = operatorStack.size() - 1; i > 0; i--) {
            operandQueue.add(operatorStack.pop());
        }
        
        return operandQueue;
    }
    

    /**
     * @param expression 算数表达式
     * @return
     * 得到表达式的结果
     */
    public double getResult(String expression) {
    	Queue<String> suffixQueue = toSuffix(expression);
    	Stack<String> suffixStack = new Stack<String>();
    	String current = "";
    	double frontOperand;
    	double backOperand;
    	double value = 0;
    	for (int i = suffixQueue.size(); i > 0; i--) {
    		current = suffixQueue.poll();
    		//如果是数字,入栈
			if (current.matches("^\\d+(\\.\\d+)*$")) {
				suffixStack.push(current);
			} else {
				backOperand = Double.valueOf(suffixStack.pop());
				frontOperand = Double.valueOf(suffixStack.pop());
				if (current.equals("+")) {
					value = frontOperand + backOperand;
				} else if (current.equals("-")) {
					value = frontOperand - backOperand;
				} else if (current.equals("*")) {
					value = frontOperand * backOperand;
				} else if (current.equals("/")) {
					try {
						value = frontOperand / backOperand;
					} catch (Exception e) {
						return 0;
					}
				}
				suffixStack.push(String.valueOf(value));
			}
		}
    	String result = suffixStack.get(0);
    	return Double.valueOf(result);
    }

}

单元测试代码如下:

package cn.tzy.calculator;

import java.util.Queue;

import org.junit.Assert;
import org.junit.Test;

public class CalculatorTest {

	private Calculator calculator;
	private String infix;

	public CalculatorTest() {
		this.calculator = new Calculator();
		this.infix = "(8+9*10)-4/2+3";
	}

	@Test
	public void testToSuffix() {
		Queue<String> suffix = calculator.toSuffix(infix);
		for (int i = suffix.size(); i > 0; i--) {
			System.out.print("(" + suffix.poll() + ")");
		}
	}
	
	@Test
	public void testGetResult() {
		double result = calculator.getResult(infix);
		Assert.assertEquals(result, 99, 0);
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++函数指针和std::function对象

    这篇博文中通过实现对String字符串大小写转换为列来说明C++中函数指针和std::function对象的使用。

    卡尔曼和玻尔兹曼谁曼
  • 时期和ANSI Date之间的转换

    一个具体日期的ANSI Date指的是该日期到1600年12月31日经过的天数。 1601年1月1日的ANSI Date为1。 在Linux中使用如下命...

    卡尔曼和玻尔兹曼谁曼
  • macOS下安装ENVI

    然后安装依赖的软件: 1. Java6 下载 - Java for OS X 2015-001 2. XQuartz https://www.xquar...

    卡尔曼和玻尔兹曼谁曼
  • Mac下golang实现Java加密方式调用

    安装完毕会在home目录下usr/local/go默认的安装目录。然后这个时候可以配置下环境变量

    小诚信驿站
  • application.yml与bootstrap.yml的区别

    Spring Cloud 构建于 Spring Boot 之上,在 Spring Boot 中有两种上下文,一种是 bootstrap,另外一种是 applic...

    Java架构师必看
  • base64编码在silverlight中的使用

    在传统的.net应用中,使用base64编码字符串是一件很轻松的事情,比如下面这段代码演示了如何将本地文件转化为base64字符串,并且将base64字符串又还...

    菩提树下的杨过
  • 听说:微软允许用户自行制作逼格超高的AR版PPT?

    信息化时代的当下,人与人之间的沟通讲究直接与高效,对于追求效益的企业来说更是如此。如何让客户快速了解公司及相关产品,那么你可能需要一份视觉美观、逻辑清晰的PPT...

    VRPinea
  • 迁移中的企业科技新范式|商业洞见

    [摘要] 科技现在已经成为商业变革必不可少的推动力量,引领着我们从数字时代进入后数字时代。演进中的交互、增强人类效能、平台的兴起、安全和机器人的崛起这五个宏观板...

    ThoughtWorks
  • IDEA 公司真牛逼,发行适合程序员编程字体

    JetBrains今天推出了一种新字体,即JetBrains Mono,它是专为开发人员设计的。

    芋道源码
  • 一个IT人眼里的“云丰杯”全国逆向物流设计大赛

    6月底的上海,空气粘湿,闷热异常,用古龙的话来说就是"空气像是牛肉汤上凝固的油脂"。而比天气更热烈的,则是在上海大学举办的第二届全国逆向物流设计大赛。

    盆盆

扫码关注云+社区

领取腾讯云代金券