java实现中缀表达式转后缀的方法
本文先给出思路与方法，最后将给出完整代码：
算法综述：
一、中缀表达式转后缀表达式：
1.中缀表达式要转后缀表达式，首先需要两个Stack（栈），其中一个应用于存放字符，另一个用于存放数字。
2.读到数字直接存入数字栈中，读到字符时，要咸鱼栈内前一元素（字符）进行比较，当当前（要存入的字符）优先级大于迁移字符时才存入，否则（>=）要仿佛将栈内元素弹出，并依次存入数字栈中。
提示：‘（' 的优先级默认比所有字符都小。所有字符都可以存在它后面；同时夜笔所有字符都大，可以存在所有字符后面
3.遇到 ‘）'时将栈内所有字符依次弹出，并存入数字栈中，知道遇到 ‘（' 为止
4.当所有字符、数字访问完毕时，栈内很可能还会有剩余的字符，这是将他们一次弹出，并纯如数字栈中
小技巧：
1.存放‘+'，‘-'时，如果只有当前一个数位空或者‘（' 时才进行存入操作，否则均弹出。
2.存放 ‘*'，‘/' 时，只有当前一个数位 ‘*'，‘/' 时才弹出其他情况下，均存入。
附上代码：
/*
* 中缀转后缀
*/
public void toPostfix() {
// TODO Auto-generated method stub
int sum = 0 ;//用于记入”（）“总个数
int j = 0 ;//用于读到”）“时循环出栈
String outStack = null;
charnum.push(null);
for( int i = 0 ; i < calculateLength ; i ++){
if ( calculate[i].equals("(")) {
charnum.push(calculate[i]);
sum ++ ;
}else if ( calculate[i].equals(")") ) {
outStack = charnum.pop();//进入前先出一个
while ( !outStack.equals("(") ){
num.push(outStack);
outStack = charnum.pop();
}//最后一次outStack正好接到”（“不入栈
sum ++ ;
}else if (calculate[i].equals("*")) {
outStack = charnum.pop();
charnum.push(outStack);
while( ( outStack == "*" || outStack == "/" ) && !(outStack == null) ){
num.push(outStack);
charnum.pop();//由于前第三行又将outStack存入栈中，座椅此处再次弹出
outStack = charnum.pop();
charnum.push(outStack);
}
charnum.push("*");
}else if (calculate[i].equals("/")) {
outStack = charnum.pop();
charnum.push(outStack);
while( ( outStack == "*" || outStack == "/" ) && !(outStack == null) ){
num.push(outStack);
charnum.pop();//由于前第三行又将outStack存入栈中，座椅此处再次弹出
outStack = charnum.pop();
charnum.push(outStack);
}
charnum.push("/");
}else if (calculate[i].equals("+")) {
outStack = charnum.pop();
charnum.push(outStack);
while( !(outStack=="(") && !(outStack == null) ){
num.push(outStack);
charnum.pop();
outStack = charnum.pop();
charnum.push(outStack);
}
charnum.push("+");
}else if (calculate[i].equals("-")) {
outStack = charnum.pop();
charnum.push(outStack);
while( !(outStack=="(") && !(outStack == null) ){
num.push(outStack);
charnum.pop();
outStack = charnum.pop();
charnum.push(outStack);
}
charnum.push("-");
}else {
num.push(calculate[i]);
}
}
outStack = charnum.pop();
while ( outStack != null ) {
num.push(outStack);
outStack = charnum.pop();
}
calculateLength = calculateLength - sum ;
Stack<String> zanshi = new Stack<>();
for(int i = 0 ; i < calculateLength ; i ++ ){
zanshi.push(num.pop());
}
CalculateToZero();
for(int i = 0 ; i < calculateLength ;i ++ ){
calculate[i] = zanshi.pop();
}
}
二、后缀表达式计算
后缀表达式计算只遵循一个原则：
首先将表达式存在栈中
遇到符号时弹出两个相应的数字，进行计算后再次 存入栈内
最后栈内身下的唯一一个数，就是所要求的结果
/*
* 后缀表达式求值
*/
public String postfix() {
int a = 0 , b = 0;//栈中弹出的两数
int sum ;//求两数运算
for (int i = 0; i < calculateLength ; i++ ) {
if (i == 0) {
num.push(calculate[i]);
}else if (calculate[i].equals("+") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a + b ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("-") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a - b ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("*") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a * b ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("/") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a / b ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("%") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a / b ;
num.push(String.valueOf(sum));
}else {
num.push(calculate[i]);
}
}
return num.pop();
}
}
最后附上完整代码
//注：代码中有很多输出 方便读者实时查看运算过程中 各内容
// 这些输出导致篇幅较长 大家看明白后 删去即可
public class Text {
Stack<String> num = new Stack<>(); //后缀用栈 中转后数字栈
Stack<String> charnum = new Stack<>();//中转后字符栈
String []calculate = new String[1000];//存字符串数组
int calculateLength = 0 ;//字符串数组长度
public Text() {
// TODO Auto-generated constructor stub
}
//转字符串数组
public void toStringArray(String input) {
char charArray[] = input.toCharArray();
int number = 0;//用于导入多位数
int j = 0 ;//用于计入当前字符串数组的位数
System.out.println(charArray.length);
for(int i = 0 ; i < charArray.length ; i++){
if(charArray[i] == '('){
calculate[j++] = "(";
}else if(charArray[i] == ')'){
calculate[j++] = ")";
}else if (charArray[i] == '+') {
calculate[j++] = "+";
}else if (charArray[i] == '-') {
calculate[j++] = "-";
}else if (charArray[i] == '*') {
calculate[j++] = "*";
}else if (charArray[i] == '/') {
calculate[j++] = "/";
}else if (charArray[i] == '%') {
calculate[j++] = "%";
}else if (charArray[i] == '#') {
calculate[j++] = "#";
}else {
String str=String.valueOf(charArray[i]);
number = number * 10 + Integer.parseInt(str);System.out.println("123");
if( (i + 1) == charArray.length || charArray[i+1] < '0' || charArray[i+1] > '9'){
if ( (i + 1) != charArray.length && charArray[i+1] == ' ') {
System.out.println("456");i++;
}
calculate[j++] = String.valueOf(number);
System.out.println(number);
number = 0 ;
}
}
System.out.println("---z->" + calculate[i]);
}
calculateLength = j-- ;//不--会将‘#'存入
}
public void outPutCalculate() {
for(int i = 0 ; i < calculateLength ; i ++ ){
System.out.println(calculate[i]);
}
}
public void CalculateToZero() {
for(int i = 0 ; i < calculateLength ; i ++ ){
calculate[i]= calculate[999] ;
}
}
//中缀转后缀
public void toPostfix() {
// TODO Auto-generated method stub
System.out.println("789");
int sum = 0 ;//用于记入”（）“总个数
int j = 0 ;//用于读到”）“时循环出栈
String outStack = null;
charnum.push(null);
System.out.println(calculateLength);
for( int i = 0 ; i < calculateLength ; i ++){
System.out.println(calculate[i]);//-----------------------------
if ( calculate[i].equals("(")) {
charnum.push(calculate[i]);
System.out.println("1-1 charpush " + calculate[i]);//-----------------------------
sum ++ ;
}else if ( calculate[i].equals(")") ) {
System.out.println("2-1 charpush " + calculate[i]);//-----------------------------
outStack = charnum.pop();//进入前先出一个
System.out.println("2-1 charpush " + outStack);//-----------------------------
while ( !outStack.equals("(") ){
System.out.println("2-2 charpush " + outStack);//-----------------------------
num.push(outStack);
outStack = charnum.pop();
}//最后一次outStack正好接到”（“不入栈
System.out.println("qiangxing 1 = " + outStack );
// outStack = charnum.pop();
System.out.println("qiangxing 2 = " + outStack );
sum ++ ;
}else if (calculate[i].equals("*")) {
outStack = charnum.pop();
charnum.push(outStack);
System.out.println("3-2 charpush " + outStack);//-----------------------------
while( ( outStack == "*" || outStack == "/" ) && !(outStack == null) ){
System.out.println("3-1 charpush " + outStack);//-----------------------------
num.push(outStack);
charnum.pop();//由于前第三行又将outStack存入栈中，座椅此处再次弹出
outStack = charnum.pop();
charnum.push(outStack);
}
System.out.println("3-3 charpush " + outStack);//-----------------------------
charnum.push("*");
}else if (calculate[i].equals("/")) {
System.out.println("5-1-0 charpush " + "1-1-1-1-1-1-1-1");//-----------------------------
outStack = charnum.pop();
System.out.println("5-1-1 charpush " + "2-2-2-2-2-2-22-2");//-----------------------------
charnum.push(outStack);
System.out.println("4-1 charpush " + outStack);//-----------------------------
while( ( outStack == "*" || outStack == "/" ) && !(outStack == null) ){
System.out.println("4-2 charpush " + outStack);//-----------------------------
num.push(outStack);
charnum.pop();//由于前第三行又将outStack存入栈中，座椅此处再次弹出
outStack = charnum.pop();
charnum.push(outStack);
}
System.out.println("4-3 charpush " + outStack);//-----------------------------
System.out.println("5-1-2 charpush " + outStack);//-----------------------------
charnum.push("/");
}else if (calculate[i].equals("+")) {
outStack = charnum.pop();
charnum.push(outStack);
System.out.println("5-1 charpush " + outStack);//-----------------------------
while( !(outStack=="(") && !(outStack == null) ){
System.out.println("5-2 charpush " + outStack);//-----------------------------
num.push(outStack);
charnum.pop();
outStack = charnum.pop();
charnum.push(outStack);
}
System.out.println("5-3 charpush " + outStack);//-----------------------------
charnum.push("+");
}else if (calculate[i].equals("-")) {
outStack = charnum.pop();
charnum.push(outStack);
System.out.println("6-1 charpush " + outStack);//-----------------------------
while( !(outStack=="(") && !(outStack == null) ){
System.out.println("6-2 charpush " + outStack);//-----------------------------
num.push(outStack);
charnum.pop();
outStack = charnum.pop();
charnum.push(outStack);
}
System.out.println("6-3 charpush " + outStack);//-----------------------------
charnum.push("-");
}else {
System.out.println("7-7 " + calculate[i]);
num.push(calculate[i]);
}
}
System.out.println("匹配结束" + outStack);
outStack = charnum.pop();
System.out.println("finish 1 == " + outStack);
while ( outStack != null ) {
num.push(outStack);
outStack = charnum.pop();
System.out.println("finish 2 == " + outStack);
}
calculateLength = calculateLength - sum ;
System.out.println( "0.0.0.0 charpush " );//-----------------------------
System.out.println("sum = " + sum + " calculate = " +
calculateLength + "calculateLength-sum = " + (calculateLength-sum));
System.out.println("over ~~~~~0 ");
Stack<String> zanshi = new Stack<>();
// num.pop();
for(int i = 0 ; i < calculateLength ; i ++ ){
zanshi.push(num.pop());
// System.out.println(num.pop());
}
CalculateToZero();
System.out.println("over ~~~~~1 ");
for(int i = 0 ; i < calculateLength ;i ++ ){
calculate[i] = zanshi.pop();
}
System.out.println("over ~~~~~2 ");
for(int i = 0 ; i < calculateLength ;i ++ ){
System.out.println(calculate[i]);
}
System.out.println("over ~~~~~3 ");
// num.push("#");
}
//后缀计算
public String postfix() {
int a = 0 , b = 0;//栈中弹出的两数
int sum ;//求两数运算
for (int i = 0; i < calculateLength ; i++ ) {
// System.out.println("目前符号：" + calculate[i]);
if (i == 0) {
num.push(calculate[i]);
}else if (calculate[i].equals("+") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a + b ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("-") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a - b ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("*") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a * b ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("/") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a / b ;
num.push(String.valueOf(sum));
}else if (calculate[i].equals("%") ) {
b = Integer.parseInt(num.pop());
a = Integer.parseInt(num.pop());
sum = a / b ;
num.push(String.valueOf(sum));
}else {
num.push(calculate[i]);
}
}
return num.pop();
}
}
结果如下：
一、前缀转后缀并输出
其中over前为转化后的后缀表达式
over后为计算结果
public class Main {
public static void main(String[] args) {
Text text = new Text();
text.toStringArray("1+2*(3-1+2)-3");
text.outPutCalculate();
text.toPostfix();
System.out.println(text.postfix());
}
}
二、后缀直接输出
注意后缀表达式时
为了实现多位数运算，连续输入一串数时 ，输入完一个数加空格
如：要计算："1+2*(3-1+2)-3" 则输入："1 2 3 1-2+*+3-"
例：
public class Main {
public static void main(String[] args) {
Text text = new Text();
text.toStringArray("1 2 3 1-2+*+3-");
text.outPutCalculate();
System.out.println(text.postfix());
}
}
输出结果：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。
相关推荐
-
Java正则表达式处理特殊字符转义的方法
正则需要转义字符 '$', '(', ')', '*', '+', '.', '[', ']', '?', '\\', '^', '{', '}', '|' 异常现象: java.util.regex.PatternSyntaxException: Dangling meta. character '*' near index 0 解决方法 对特殊字符加\\转义即可. 注意:虽然使用[]在部分条件下也可以,但是在对于(.[.{范围边界开始符不匹配的情况下会报如下: 异常现象 java.util.
-
JAXB命名空间及前缀_动力节点Java学院整理
本文讲解使用jaxb结合dom4j的XMLFilterImpl过滤器实现序列化和反序列化的完全控制 主要实现以下功能 序列化及反序列化时忽略命名空间 序列化时使用@XmlRootElement(namespace="http://www.lzrabbit.cn")注解作为类的默认命名空间,彻底消除命名空间前缀 序列化时引用类有不同命名空间时也不会生成命名空间前缀,而是在具体的xml节点上添加相应的xmlns声明 其它的xml节点命名及命名空间需求 同一个包下有多个命名空间
-
Java后缀数组之求sa数组的实例代码
后缀数组的一些基本概念请自行百度,简单来说后缀数组就是一个字符串所有后缀大小排序后的一个集合,然后我们根据后缀数组的一些性质就可以实现各种需求. public class MySuffixArrayTest { public char[] suffix;//原始字符串 public int n;//字符串长度 public int[] rank;// Suffix[i]在所有后缀中的排名 public int[] sa;// 满足Suffix[SA[1]] < Suffix[SA[2]] --
-
关于各种排列组合java算法实现方法
一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用 复制代码 代码如下: import java.util.Arrays; //利用二进制算法进行全排列//count1:170187//count2:291656 public class test { public static void main(String[] args) { long start=System.currentTimeMillis(); count
-
java实现任意四则运算表达式求值算法
本文实例讲述了java实现任意四则运算表达式求值算法.分享给大家供大家参考.具体分析如下: 该程序用于计算任意四则运算表达式.如 4 * ( 10 + 2 ) + 1 的结果应该为 49. 算法说明: 1. 首先定义运算符优先级.我们用一个 Map<String, Map<String, String>> 来保存优先级表.这样我们就可以通过下面的方式来计算两个运算符的优先级了: /** * 查表得到op1和op2的优先级 * @param op1 运算符1 * @param op2
-
java异或加密算法
简单异或密码(simple XOR cipher)是密码学中中一种简单的加密算法. 异或运算:m^n^n = m; 利用异或运算的特点,可以对数据进行简单的加密和解密. 复制代码 代码如下: /** * 简单异或加密解密算法 * @param str 要加密的字符串 * @return */private static String encode2(String str) { int code = 112; // 密钥 char[] charArray = str.toCharArray();
-
java字符串相似度算法
本文实例讲述了java字符串相似度算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: public class Levenshtein { private int compare(String str, String target) { int d[][]; // 矩阵 int n = str.length(); int m = target.length(); int i; // 遍历str的
-
Java实现几种常见排序算法代码
稳定度(稳定性)一个排序算法是稳定的,就是当有两个相等记录的关键字R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前. 排序算法分类 常见的有插入(插入排序/希尔排序).交换(冒泡排序/快速排序).选择(选择排序).合并(归并排序)等. 一.插入排序 插入排序(Insertion Sort),它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),
-
java数据结构与算法之中缀表达式转为后缀表达式的方法
本文实例讲述了java数据结构与算法之中缀表达式转为后缀表达式的方法.分享给大家供大家参考,具体如下: //stack public class StackX { private int top; private char[] stackArray; private int maxSize; //constructor public StackX(int maxSize){ this.maxSize = maxSize; this.top = -1; stackArray = new char[
-
Java中缀表达式转后缀表达式实现方法详解
本文实例讲述了Java中缀表达式转后缀表达式实现方法.分享给大家供大家参考,具体如下: 本文先给出思路与方法,最后将给出完整代码 项目实战: https://www.jb51.net/article/158335.htm 算法综述: 一.中缀表达式转后缀表达式: 1.中缀表达式要转后缀表达式,首先需要两个Stack(栈),其中一个应用于存放字符,另一个用于存放数字. 2.读到数字直接存入数字栈中,读到字符时,要咸鱼栈内前一元素(字符)进行比较,当当前(要存入的字符)优先级大于迁移字符时才存入,否