精华内容
下载资源
问答
  • 后缀转中缀

    千次阅读 2017-09-02 21:04:01
    后缀转中缀:  eg: 652 3+8*+3+* >>> 6*((5+(2+3)*8)+3) 实现: ·读入表达式,若是数字压入栈; ·若是运算符,则弹出栈顶的两个元素a、b进行 b operator a,后再压入栈中即可; ·...

    兄弟篇 中缀转后缀 + 后缀计算


    后缀转中缀:

     eg:   652 3+8*+3+*   >>> 6*((5+(2+3)*8)+3)

    实现:

    ·读入表达式,若是数字压入栈;

    ·若是运算符,则弹出栈顶的两个元素a、b进行 b operator a,后再压入栈中即可;

    ·循环至最后,返回栈顶元素,即为所需要的后缀表达式。

    时间复杂度: O(N)


    代码如下:

    //后缀转中缀
    string postfixTOinfix(const string s)
    {
    	string a, b;
    	stack mark;
    	for (size_t i = 0; i < s.length(); ++i) {
    		if (isalnum(s[i]))
    			mark.push(to_string(s[i] - '0'));
    		else
    			switch (s[i])
    			{
    			case '+':
    				a = mark.top(); mark.pop(); b = mark.top(); mark.pop();
    				mark.push("(" + b + "+" + a + ")"); 
    				break;
    			case ' - ':
    				a = mark.top(); mark.pop(); b = mark.top(); mark.pop();
    				mark.push("(" + b + "-" + a + ")"); 
    				break;
    			case '*': a = mark.top(); mark.pop(); b = mark.top(); mark.pop();
    				mark.push(b + "*" + a); 
    				break;
    			case ' / ': a = mark.top(); mark.pop(); b = mark.top(); mark.pop();
    				mark.push(b + "/" + a); 
    				break;
    			default:
    				break;
    			}
    	}
    	return mark.top();
    }


    展开全文
  • java后缀转中缀

    2012-07-29 10:33:30
    不用堆栈,简单的数组递归实现高效高效Java表达式后缀转中缀
  • 最近一直在看数据结构这本书,我相信,对于每个程序员来说,数据结构都尤为重要。... 直入主题:将中缀表达式转为...关于后缀转中缀,中缀转后缀的理论介绍,请先阅读其互转的理论知识,或者我转发的这篇文章,这里不再累

    最近一直在看数据结构这本书,我相信,对于每个程序员来说,数据结构都尤为重要。为什么要学,可以看看这位博友的认识http://blog.csdn.net/sdkfjksf/article/details/54380659

    直入主题:将缀表达式转为后缀表达式 以及后缀表达式转为前缀表达式的实现。

    关于后缀转中缀,中缀转后缀的理论介绍,请先阅读其互转的理论知识,或者我转发的这篇文章,这里不再累赘,最好参考《数据结构与算法描述java语言版》,接下来将会用java写。


    一、首先,怎么实现缀表达式转为后缀表达式

    缀表达式转为后缀表达式相对较为简单,对于中缀表达式转后缀,其思想是将 运算符(+-*/)往栈中放,数字就直接输出,然后通过每次扫描遇到的运算符优先级来判断出栈与入栈。直接上代码吧,代码中也有解释!

    package com.liyongdada.cn;
    
    import java.util.Scanner;
    import java.util.Stack;
    
    public class StackTest {
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Character token;
    		String exep;
    		int i=0;
    		//下面一句需要jre1.5
    		Stack<Character> s=new Stack<Character>();
    		Scanner sc=new Scanner(System.in);
    		exep=sc.next();
    		while((token=exep.charAt(i++))!='='){
    			if(token>='a' && token<='z'){
    				System.out.print(token+" ");
    			}else{
    				switch(token){
    				case '+' :
    					//省略掉的同时没写break;是因为,只要是小于或者等于的都会出栈,因此,继续执行下面语句
    				case '-' :
    					while(!s.isEmpty() && s.peek()!='('){
    						System.out.print(s.pop()+" ");
    					}
    					s.push(token);
    					break;
    				case '*' :
    				case '/' :
    					while(!s.isEmpty() && s.peek()!='(' && s.peek()!='+' && s.peek()!='-'){
    						System.out.print(s.pop()+" ");
    					}
    					s.push(token);
    					break;
    				case '(' :
    					s.push(token);
    					break;
    				case ')' :
    					while (!s.isEmpty() && s.peek()!='('){
    						System.out.print(s.pop()+" ");
    					}
    					s.pop();
    					break;
    				case '^' :
    					while (!s.isEmpty() && !(s.peek()=='(' || s.peek()=='^')){
    						System.out.print(s.pop()+" ");
    					}
    					s.push(token);
    					break;
    				}
    			}
    		}
    		//最后检测,将剩余的全部出栈
    		while (!s.isEmpty()){
    			System.out.print(s.pop()+" ");
    		}
    	}
    
    }

    二、后缀表达式转换为中缀表达式代码

    首先,区别一下,这个后缀表达式转换为中缀表达式与前面不同,这里进行出入栈操作的是数字,而不是运算符。自己在网上找了很久,没发现有人写出这种转法的java代码,也许是没人放出来吧。于是,自己动手写了一个。思想与中缀表达式转换为后缀表达式有点不同。具体看代码吧!

    首先,我的思想是,将一个表达式中的运算符取出并用一个数组存储,对于怎么自动加括号,通过判断下一个运算符优先级。

    (假如: 有   6523+8*+3+*      我们很容易计算得到其中缀表达式为   ((3+2)*8+5+3)*6,所以,由第一个运算符  ”+“的下一个运算符 "*", 便可以知道,其 3+2 需要用括号括起来。其他方式也是,具体看代码。 )。最后,算法不是特别完美,欢迎指正!

    package com.liyongdada.cn;
    
    import java.util.Scanner;
    import java.util.Stack;
    
    public class HouToZhong {
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		String expp;// 接收输入的表达式
    		String token;
    		int i = 0;
    		int ssLength = 0;// 记录运算符数组的大小
    		int charIndex = 0; // 用于记录已输出运算符的个数
    		Scanner sc = new Scanner(System.in);
    		expp = sc.next();
    		//计算表达式中,有多少个运算符
    		for (int j = 0; j < expp.length(); j++) {
    			if (!Character.isDigit(expp.charAt(j))) {
    				ssLength += 1;
    			}
    		}
    		//定义大小
    		char[] ss = new char[ssLength];
    		int sj = 0;
    		//依次赋值
    		for (int j = 0; j < expp.length(); j++) {
    			if (!Character.isDigit(expp.charAt(j))) {
    				ss[sj++] = expp.charAt(j);
    			}
    		}
    		//泛型为String类型,这可以避免每次复写掉
    		Stack<String> s = new Stack<String>();
    		String pop1, pop2;//用于接收每次取出的栈顶字符串
    		while (!(token = expp.substring(i, ++i)).equals("=")) {
    			if (token.matches("[0-9]?")) {
    				s.push(token);
    			} else {
    				// 只有jre1.7才能使用字符串作为switch中的值
    				switch (token.charAt(0)) {
    				case '+':
    					if (charIndex < ssLength - 1) {
    						pop1 = s.pop();
    						pop2 = s.pop();
    						if (ss[charIndex + 1] == '*'
    								|| ss[charIndex + 1] == '/') {
    							//调用自定义方法
    							s.push(mixExpp(pop2, pop1, "+"));
    						} else
    							s.push(pop2 + "+" + pop1);
    					} else {
    						System.out.println("执行错误!+!");
    						return;
    					}
    					charIndex++;
    					break;
    				case '-':
    					if (charIndex < ssLength - 1) {
    						pop1 = s.pop();
    						pop2 = s.pop();
    						if (!(ss[charIndex + 1] != '*' || ss[charIndex + 1] != '/')) {
    							s.push(mixExpp(pop2, pop1, "-"));
    						} else
    							s.push(pop2 + "-" + pop1);
    					} else {
    						System.out.println("执行错误!-!");
    						return;
    					}
    					charIndex++;
    					break;
    				case '*':
    					pop1 = s.pop();
    					pop2 = s.pop();
    					s.push(pop2 + "*" + pop1);
    					charIndex++;
    					break;
    				case '/':
    					pop1 = s.pop();
    					pop2 = s.pop();
    					s.push(pop1 + "/" + pop2);
    					charIndex++;
    					break;
    				case '^':
    					pop1 = s.pop();
    					pop2 = s.pop();
    					s.push(pop2 + "^" + pop1);
    					charIndex++;
    					break;
    				}
    			}
    		}
    		// 取出最后一个
    		System.out.println(s.pop());
    	}
    
    	// 用于拼接括号的方法
    	public static String mixExpp(String one, String two, String fuhao) {
    		String str = "(" + one + fuhao + two + ")";
    		return str;
    	}
    
    }


    展开全文
  • 一、中缀表达式转后缀表达式思路:1)将中缀表达式存储到一个List当中 2)将中缀表达式List后缀表达式对应的List1)代码实现//将中缀表达式装到List当中 public static List<String> toInfixList(String ...

    一、中缀表达式转后缀表达式

    思路:1)将中缀表达式存储到一个List当中

    2)将中缀表达式List转成后缀表达式对应的List

    1)代码实现

    //将中缀表达式装到List当中

    public static List<String> toInfixList(String infix){

    List<String> infixList = new ArrayList<String>();

    int i = 0;//指针,用于遍历中缀字符串

    String str = "";//用于多位数的拼接

    char ch;//用于存放遍历出来的每一个字符

    do{

    //如果c是一个非数字,直接添加到List中,数字在阿斯卡码表中的区间是48[0]到57[9]

    if((ch=infix.charAt(i)) < 48 || (ch=infix.charAt(i)) > 57){

    infixList.add(ch+"");

    i++;

    }else{//如果为数字,要考虑到多位数的问题,进行字符串的拼接

    str = "";//每次进行多位数拼接之前要将上一次拼接的多位数置空

    while(i < infix.length() && (ch=infix.charAt(i)) >= 48 && (ch=infix.charAt(i)) <= 57){

    str += ch;

    i++;

    }

    infixList.add(str);

    }

    }while(i < infix.length());

    return infixList;

    }

    2)代码实现

    c610b006ac277e6851836b98f1dc3e11.png

    //将中缀表达式List转成后缀表达式对应的List:思路用栈说明,代码使用List实现

    public static List<String> toSuffixList(List<String> infixList){

    Stack<String> s1 = new Stack<String>();//符号栈

    /**

    * 因为在中缀转后缀的过程中,s2至始至终都在存放东西,而没有pop的操作,

    * 并且在后期还需要逆序进行运算,可以使用List替代较为方便

    * */

    List<String> s2 = new ArrayList<String>();

    for(String item:infixList){

    //如果是一个数,则加入s2

    if(item.matches("d+")){

    s2.add(item);

    }else if(item.equals("(")){

    s1.push(item);

    }else if(item.equals(")")){

    while(!s1.peek().equals("(")){

    s2.add(s1.pop());

    }

    s1.pop();//消除括号

    }else{

    while(s1.size() != 0 && Operation.getPriority(s1.peek()) >= Operation.getPriority(item)){

    s2.add(s1.pop());

    }

    //还需要将item压入栈中

    s1.push(item);

    }

    }

    //将s1中剩余的元素加入到s2中

    while(s1.size() != 0){

    s2.add(s1.pop());

    }

    return s2;

    }

    二、后缀表达式的计算

    e7630ce9572e36e7761d4de31a8ce5fd.png

    //传入一个List,返回一个结果

    /**

    * 思路:遍历list,如果是数字则压入栈中,如果是操作符则pop出两个数字,运算结果压入栈中

    * */

    public static int cal(List<String> ls){

    Stack<String> stack = new Stack<String>();//注意是存储字符串的栈

    //遍历ls

    for(String item:ls){

    //使用正则表达式取出数

    if(item.matches("d+")){

    stack.push(item);

    }else{

    int num2 = Integer.parseInt(stack.pop());

    int num1 = Integer.parseInt(stack.pop());

    int res = 0;

    switch (item) {

    case "+":

    res = num1 + num2;

    break;

    case "-":

    res = num1 - num2;

    break;

    case "*":

    res = num1 * num2;

    break;

    case "/":

    res = num1 / num2;

    break;

    default:

    break;

    }

    stack.push(res+"");//将结果类型转成字符串

    }

    }

    return Integer.parseInt(stack.pop());

    }

    }

    展开全文
  • 我正在实现中缀后缀,但无法调试程序中的错误。我执行join操作的最后一个返回语句的输入类型是NONE。当我开始调试时,我发现在这部分代码中,第一个push操作(for*)之后出现了问题。之后,当我对它执行pop()时,它...

    我已经开始用Python解决数据结构问题。我正在实现中缀到后缀,但无法调试程序中的错误。我执行join操作的最后一个返回语句的输入类型是NONE。

    当我开始调试时,我发现在这部分代码中,第一个push操作(for*)之后出现了问题。之后,当我对它执行pop()时,它将不返回任何值,而不是返回*。有人能指出,这里有什么错吗?*else:

    while (not s.isEmpty()) and (prec[s.peek()] >= prec[token]):

    #print token

    outlst.append(s.pop())

    #print outlst

    s.push(token)

    print (s.peek())*

    中缀到后缀转换:from StackClass import StackClass

    def infixtopostfix(infixexpr):

    s=StackClass()

    outlst=[]

    prec={}

    prec['/']=3

    prec['*']=3

    prec['+']=2

    prec['-']=2

    prec['(']=1

    oplst=['/','*','+','-']

    tokenlst=infixexpr.split()

    for token in tokenlst:

    if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token in '0123456789':

    outlst.append(token)

    elif token == '(':

    s.push(token)

    elif token == ')':

    topToken=s.pop()

    while topToken != '(':

    outlst.append(topToken)

    topToken=s.pop()

    else:

    while (not s.isEmpty()) and (prec[s.peek()] >= prec[token]):

    #print token

    outlst.append(s.pop())

    #print outlst

    s.push(token)

    print (s.peek())

    while not s.isEmpty():

    opToken=s.pop()

    outlst.append(opToken)

    #print outlst

    return outlst

    #return " ".join(outlst)

    print (infixtopostfix("A * B + C * D"))

    展开全文
  • 大家看到,后缀表达式适合计算式进行运算,但是人却不太容易写出来,尤其是表达式很长的情况下,因此在开发中,我们需要将 中缀表达式后缀表达式。具体步骤如下:1.初始化两个栈:运算符栈s1和储存中间结果的栈s2...
  • 我试图在python中创建一个用于家庭作业的中缀后缀的转换器,我在网上找到了多个看起来足够简单的转换器,但没有一个满足我需要的要求。我必须使用以下课程:class Token(object):UNKNOWN = 0 # unknownINT = 4 # ...
  • 后缀转中缀C语言实现

    2010-04-20 19:17:22
    将由数字和四则运算符组成的后缀表达式变换为中缀表达式。输入的后缀表达式包含的运算符不超过15个。要求转换后的中缀表达式中不应出现不必要的括号。例如,整个表达式两端的括号要省略,不影响原计算顺序的括号要...
  • 南故笙烟:中缀表达式转为后缀表达式​zhuanlan.zhihu.com思路分析1.初始化两个栈:运算符栈s1和储存中间结果的栈s22.从左至右扫描中缀表达式3.遇到操作数时,将其压入s24.遇到运算符时,比较与s1栈顶运算的优先级*...
  • 命题公式后缀转中缀

    2019-11-12 22:04:16
    /* 求任意一个命题公式的真值表(B),并根据真值表求主范式(C)*/ // p、 q、 r、 () 、 &(∧)、 |(∨)、 > (->蕴含) 、 -(等价) ! (﹁否定) ... //中缀转后缀 cout; } return 0; }
  • 1、传入参数,这里用的复杂一点的 2、 实例化、创建最终生成后缀样式的 列表、将传入的字符串分隔开 3、当token==“(”时,opstack中存入“(”,因为转换成后缀就不需要用“()”表示优先级,存起来是用于做优先级的...
  • void change_(string &res,string &cnt)//后缀转中缀,res中由空格隔开,str中无空格和多余的括号 {  string _stack[N];//中缀表达式栈  int priority[N];//优先级,操作数 0,+ - 1,* / 2;  int top=-1;  int len=...
  • C++ 后缀转换中缀表达式

    千次阅读 2013-11-23 23:21:41
    string postToInfix() { stack s; string token; string a, b; cin>>token; while (token[0] != '=') { if (token[0] >= ’a’ && token[0] ’z’) s.push(token);
  • #define _CRT_SECURE_NO_WARNINGS #include"LinkList.c" #include<stdio.h> #include<stdlib.h> #include<string.h>...//遇到符号,取出栈的第一个元素为右操作符,第二个元素为左操作符。...
  • 鉴于有的朋友并没有看景禹之前的分享,我就把中缀表达式与后缀表达式做简单的科普。中缀表达式简单来说就是我们小学课本中常见的那种形式,也就是我们人所习惯...今日分享的是中缀表达式转后缀表达式的执行过程,为...
  • 中缀转后缀表达式 中缀转后缀表达式 中缀转后缀表达式
  • 后缀表达式转中缀表达式(非常简单易懂)

    万次阅读 多人点赞 2019-06-25 20:43:59
    最近刷题,看到了很多后缀转中缀的题目,查了一些网上的教程,在这里做了一个简单详细的说明。关于中缀转后缀请看我的另外一篇博客。 后缀转中缀 举个例子~对于后缀表达式ABCD−∗+EF/−ABCD-*+EF/-ABCD−∗+EF/−,...
  • 中缀表达式转后缀表达式参考的文章就是直接给出了算法,但是算法如何推导出来的还没有弄明白,简单记录下我自己的理解,强行解释一下。后缀表达式就是操作符再操作数的后面,并且计算机能够根据简单的优先级就能进行...
  • 后缀表达式转中缀表达式的代码,请各位大神用栈来解,其他的如树等太过高深,蒟蒻一只不会用。拜托拜托!感激不尽!
  • 后缀转中缀

    2014-10-27 13:46:15
    后缀转中缀式 【问题描述】 将由数字和四则运算符组成的后缀表达式变换为中缀表达式。输入的后缀表达式包含的运算符不超过15个。要求转换后的中缀表达式中不应出现不必要的括号。例如,整个表达式两端的括号要...
  • 栈应用:中缀转后缀中缀转前缀

    千次阅读 多人点赞 2018-12-01 23:04:03
    中缀转后缀 转换过程需要用到栈,具体过程如下: 从左到右扫描字符串 1)如果遇到操作数,我们就直接将其输出(输出我们用队列保存)。 2)如果遇到操作符,当栈为空直接进栈,不为空,判断栈顶元素操作符优先级...
  • 从书上看到的讲起最近(半年内 )在看《大话数据结构》,上个星期在栈这一节看到了后缀表达式用于...后缀表达式求值规则(《大话数据结构》)中缀转后缀规则(《大话数据结构》)当尝试了之后发现,上面的描述没有...
  • 表达式的转换:1....后缀表达式转中缀表达式或者前缀表达式最简单,直接构造表达式二叉树,得到表达式树根节点,然后中序遍历和前序遍历即可3.前缀表达式转中缀表达式或者后缀表达式最简单,直接构造表...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,449
精华内容 1,779
关键字:

后缀转中缀