使用带链表的堆栈数据结构将中缀转换为后缀
使用带链表的堆栈数据结构将中缀表达式转换为后缀表达式的过程如下：
- 创建一个空的堆栈，用于存储运算符。
- 遍历中缀表达式的每个字符：
- 如果是操作数（数字或变量），直接输出到后缀表达式。
- 如果是左括号"("，将其压入堆栈。
- 如果是右括号")"，则将堆栈中的运算符依次弹出并输出到后缀表达式，直到遇到左括号为止。注意，左括号不输出到后缀表达式。
- 如果是运算符（+、-、*、/等），则：
- 如果堆栈为空，或者堆栈顶部的运算符是左括号"("，则将当前运算符压入堆栈。
- 否则，比较当前运算符与堆栈顶部运算符的优先级：
- 如果当前运算符的优先级大于堆栈顶部运算符的优先级，将当前运算符压入堆栈。
- 否则，将堆栈顶部的运算符弹出并输出到后缀表达式，然后继续比较当前运算符与新的堆栈顶部运算符的优先级，直到当前运算符的优先级大于堆栈顶部运算符的优先级，然后将当前运算符压入堆栈。
- 遍历完中缀表达式后，将堆栈中剩余的运算符依次弹出并输出到后缀表达式。
最终得到的后缀表达式即为中缀表达式的转换结果。
使用带链表的堆栈数据结构可以方便地实现中缀转后缀的算法。链表可以动态地分配内存，适应不同长度的表达式。堆栈的压入和弹出操作可以在链表的头部进行，具有较高的效率。
中缀转后缀的应用场景包括编译器、计算器等需要处理数学表达式的程序。后缀表达式更容易计算和理解，可以方便地进行运算符优先级的判断和计算。
腾讯云提供的相关产品和服务包括：
- 云服务器（CVM）：https://cloud.tencent.com/product/cvm
- 云数据库 MySQL 版（CMQ）：https://cloud.tencent.com/product/cdb
- 云原生应用引擎（TKE）：https://cloud.tencent.com/product/tke
- 人工智能平台（AI Lab）：https://cloud.tencent.com/product/ai
- 物联网开发平台（IoT Explorer）：https://cloud.tencent.com/product/iotexplorer
- 移动应用开发平台（MPS）：https://cloud.tencent.com/product/mps
- 云存储（COS）：https://cloud.tencent.com/product/cos
- 区块链服务（BCS）：https://cloud.tencent.com/product/bcs
- 腾讯云元宇宙计划：https://cloud.tencent.com/solution/virtual-universe
请注意，以上链接仅供参考，具体产品和服务选择应根据实际需求进行评估和决策。
相关·内容
2回答
对于类，我们的任务是使用“抽象中的双向链表堆栈实现”将中缀表达式转换为后缀。我能够编写一个使用Stack的程序来进行转换，但是双向链表的用途是什么呢？我们要添加到列表中的信息节点是什么？
这是作为示例提供给我们的stack类。为什么变量是下一个类型堆栈？它不应该是Node吗？
public class Stack {
private int data;
private Stack next;
private static Stack top;
//Initialize Stack
public Stack () {
top = null;
next
浏览 1提问于2015-05-07得票数 0
3回答
将堆栈解析为二叉树？
、、、
我正在编写一个程序，任务是将数学表达式(如(2+4)*(4/3) )转换为二叉树，然后对其进行操作。
首先，在解析时，我将字符串转换为两个堆栈:操作数和运算符。如果在上面的示例中，树应该是这样的，我如何确定根应该是什么：
*
/ \
+ /
/\ /\
2 4 4 3
注意，根是*，它是最外层的操作数。但在我的操作数堆栈上，它看起来是这样的：
/
*
+
而且可能会有像(2+4+3)*4或2*((4+1)/3)这样的案例。
我如何确定哪个操作数应该是我的二叉树的根？
浏览 2提问于2010-11-11得票数 2
回答已采纳
我目前正在用Java做一个简单的计算器解析器，只处理+和-运算符，以及整数。我读过关于和求值的文章，我想知道括号是否可以与这两种方法一起使用？
浏览 2提问于2010-06-29得票数 3
回答已采纳
1回答
我正在尝试做一个后缀转换器的中缀。我已经在谷歌中搜索过代码，但大多数算法都是使用堆栈或使用大量的正则表达式，或者很难理解，但我想用二叉树来实现。
下面是我已经做过的事情：
类节点：
public class Node
{
private object element;
private Node left;
private Node right;
private Node parent;
public Node()
{
}
public Node(object x, Node r, Node l)
{
e
浏览 1提问于2014-11-21得票数 3
对于我的作业，我需要使用堆栈制作计算器。我得到了加减法乘法部分。我用keno表示撤销，我只是弹出堆栈，为了清楚起见，我可以在堆栈的顶部添加一个0，但每次用户输入U或C时，程序就会崩溃，因为用户输入的应该是int。
输出：
=>1
2
+
=>3
2
-
=>1
9
*
=>9
9
/
=>1
u
=>9
c
=>0
#include <iostream>
#include <sstream>
#include <stack>
using namespace std;
int add(int a, int b)
{
浏览 0提问于2019-12-12得票数 1
2回答
我试着用c语言做一个简单的计算器，支持带括号的+，-，*和/运算符。例如，((2.1 - 5.6)*4)+(2.8+2 / 2.2)应该是-10.29...我试着这样做，但它只适用于外巴克。如果用户的输入包含括号，我不知道该如何处理。
float calc(void)
{
float x,y, parse;
char c;
int test = scanf("%f %c %f", &x,&c,&y);
if (test == 0){ // if '(' starts equation
pa
浏览 3提问于2014-06-07得票数 0
我试图‘翻译’(我的意思是python可以理解的语言) '2x^2+3'，我想得到'2*x^2 +3‘(这样python就可以理解它了)。
eq = '2x^2+3'
newlist = []
if '^' in eq:
eq = eq.replace('^', '**')
else:
print ''
for x in range (len(eq)):
newlist.append(eq [x])
print newlist
然后我得到了'2'，
浏览 1提问于2014-08-24得票数 0
2回答
我需要实现一个简单的公式解析器。我要做的是先创建一个，然后创建一个。不幸的是，此算法不允许使用括号，即(2+3)*a。有人知道如何扩展算法以允许使用括号吗？
提前谢谢你，
弗兰克
浏览 0提问于2010-07-05得票数 2
回答已采纳
我正试着用Java做一个普通的(前缀)波兰语符号计算器。我似乎不能让Java反向读取输入，并将每个整数输入到堆栈中，然后在弹出后对它们执行计算。 import java.util.Scanner;
import java.util.Stack;
public class add
{
static boolean inputIsOperator(String next) {
return (next.equals("+") || next.equals("-") || next.equals("x"));
}
浏览 7提问于2019-01-14得票数 0
回答已采纳
1回答
我正在尝试制作一个计算器，用户在一行中输入数据，然后按下"=“，它就会计算结果。但是，我不知道如何接收为计算而输入的数据。1)我是接受整个字符串并计算它(这意味着android必须能够区分+和-等符号) 2)还是在用户输入数字时逐个接受数据。到目前为止，我有这样的想法：
public void onClickButton (View view)
{
if (view.getId() == (R.id.Button01)){
txtView1.append("7");
} else if (view == f
浏览 0提问于2013-12-16得票数 0
我想为计算器编写一个键盘。我想做的是：
带有0到9个键的键盘特殊键：+-*/。=
到目前为止，我的概念是：
当一个数字键被按下时，将它的int值转换为一个字符串，并将该字符串附加到bufferString。这样一来，输入值就建立起来了。当用户按下时。(要生成浮点值)，请检查是否。已经在bufferString中了。如果是，忽略它。
但是:这真的是一个好方法吗？或者我应该做所有这些数字输入的东西纯粹的数学？
浏览 1提问于2009-11-03得票数 0
回答已采纳
2回答
我是prolog的新手，我正在尝试通过更改它们的优先级来重新分配prolog中的运算符。我在以下方面遇到了4个错误：
:-op(1000,yf,+). %unary plus%
:-op(1000,yf,-). %unary minus%
:-op(750,yfx,"%"). %modulo%
前两个给出了类似的错误，如下所示：
warning: directive failed (op(1000,xf,+)) with exception (error(permission_error(create,operator,+),op/3))
我也得到了一个模1的错
浏览 6提问于2013-02-18得票数 2
回答已采纳
1回答
调车场算法解析函数
、、、、
我正在努力让我的调车场算法的实现工作起来。它能很好地处理数字和运算符。但是，当我尝试向输入中添加函数时，就会出现问题。因为当函数参数应该输出到右边时，它会输出到函数的左边。
测试程序
public class FrontTest
{
public static void main(String[] args)
{
String str = "cbrt ( 8 )";
System.out.println(ShuntTest.infixToPostfix(str));
}
}
算法
import java.util.*;
浏览 0提问于2015-10-23得票数 1
回答已采纳
2回答
分析括号
、、、
我正在尝试用Python3做一个计算器(只是为了学习)。我希望能够(仅作为示例)从输入()中计算"5 *(2+1 )^2“。我希望能够检测到括号是否关闭或包含另一组括号。我还需要能够隔离其中的信息，以便能够以正确的顺序对其进行评估。
我意识到这可能是一段重要的代码，所以如果您能为我指出正确的方向，我将非常感激。我正在寻找文档、函数名称的链接，以及您可以提供的任何提示来帮助我。
浏览 0提问于2013-11-19得票数 1
4回答
嗯，这是语言不可知的，我更喜欢在C#或F#中做，但这次我更感兴趣的问题是“这是如何工作的”。
我想完成的是：
a)我想学习它-这一次是关于我的自我，这是为了一个有趣的项目，我想展示我自己在这方面真的很好
b)我对EBNF略知一二(虽然我还不知道EBNF中运算符优先级是如何工作的-- Irony.NET做得很对，我检查了示例，但这对我来说有点不祥)
c)我的解析器应该能够以5* (3 + (2 -9* (5 / 7)) + 9)为例，并给出正确的结果
d)坦率地说，这似乎是我在编写编译器甚至解释器时遇到的最大问题。我甚至可以生成64位汇编器代码(我可以手动编写汇编器)，但是公式解析器...
e)
浏览 0提问于2010-05-27得票数 7
5回答
我知道它们是如何相互转换的，但从来没有真正理解过它们的应用是什么。通常的中缀操作非常易读，但是它在哪里失败了，导致了前缀和后缀表示法的产生
浏览 0提问于2011-09-27得票数 40
回答已采纳
我希望看到一些标准数据结构的优秀PHP代码示例。
你知道像线性链表，堆栈，队列，二进制搜索树等类的任何代码样本吗？
浏览 0提问于2010-08-07得票数 9
回答已采纳
如果使用数组实现，我可以看到使用两个堆栈的优势，因为使用数组实现堆栈比使用队列更容易。但是如果使用链表，有什么好处呢？将堆栈弹出到队列的行为增加了链表和数组实现的开销。
浏览 0提问于2010-01-12得票数 17
回答已采纳
为什么我们需要堆栈，因为我们已经有了这么多的数据结构，它们也可以处理反向链接列表和向量中的数据管理？其他数据结构没有的堆栈有什么用处/独特之处？
另外，为什么只有数组和链表与堆栈兼容，为什么向量不能与堆栈兼容？
浏览 4提问于2022-05-12得票数 1
2回答
我需要一个使用堆栈在infix表达式中插入括号的算法。例如：
输入: 12/c+c*p^(8+9)
输出：(12/c)+(c*(p^(8+9)
我只需要这个算法，如果我们通过前缀或后缀达到输出是可以的。但是输出应该是精确的，是一个带圆括号的infix表达式。
如果有人能给出一个伪码或一步一步的例子，我会很感激的。
谢谢
浏览 0提问于2016-03-04得票数 0
4回答
堆栈中的负数
、、
我是编译器世界^_^的新学生，我想知道堆栈中的负数是合法的。
例如：
中缀: 1-5=-4后缀: 15-
这些语句是：
push(1)
push(5)
x=pop()
y=pop()
t=sub(y,x)
push(t)
堆栈中的最终结果将是(-4)
如果它是合法的，我如何表示它？？
谢谢你，^_^
浏览 0提问于2009-11-10得票数 0
3回答
我理解在前缀/后缀中，没有必要担心操作符的优先顺序。但是我们在哪里使用前缀/后缀表达式呢？它们是由编译器内部转换的吗？有没有一种方法，我可以在前缀/后缀中编写表达式，然后编译器为我计算它？
浏览 0提问于2015-07-26得票数 1
与使用传统的C结构来管理标准数据结构(如链表、堆栈、树、队列..etc )相比，使用基于C++的类/对象有什么优势？如果问题不清楚，请告诉我。
浏览 2提问于2010-06-09得票数 3
2回答
我正在做infix to post fix符号。我的程序遵守了，尽管出于某种原因，它不会接受任何中缀表达式，只接受后缀表达式，这与我想要做的相反。这是我的程序。我花了很长时间才在正确的堆栈交换组上发帖。
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
using namespace std;
string infixexpr (istream& in)
{
//Holds value in computation
stack<st
浏览 5提问于2013-12-01得票数 0
2回答
我需要实现中缀到后缀的转换算法来计算表达式a+b*c-d/e
我也需要使用queue (我认为需要两个不同的队列堆栈)
我已经使用DoubleLinkList创建了我的queue类，现在只需要为这个问题创建算法。不过，我还是不知道该怎么做。任何帮助都将不胜感激！
到目前为止(我知道这是非常错误的)，我有：
string infix = "a+b*c-d/e";
Queue *holder = new Queue();
Queue *newstring = new Queue();
int length = infix.length();
char
浏览 0提问于2013-03-15得票数 0
1回答
如何在c++中反方向编写
、、、
这是我的第一个问题，请原谅我的非技术语言
我正在制作一个程序来转换中缀到前缀和后缀。我对后缀做了中缀，这是有效的。现在，当我想插入到前缀时，我们需要颠倒表达式。所以我想从相反的方向来读infix。
while(*e != '\0')
{
if(isalpha(*e))
printf("%c ",*e);
else if(*e == '(')
push(*e);
else if(*e == ')')
{
浏览 10提问于2021-03-07得票数 0
我想在计算器中做多项运算，例如：2+3*3/7。如何做到这点。有人能帮我吗？计算器的单一操作就能工作。
如何在一个editText中计算多个操作。这段代码是在相等的按钮点击方法上添加的。
下面是我的代码：
btnEqualto.setOnClickListener(new OnClickListener()
{
@Override
public void onClick(View v)
{
String str2 = edtxt.getText().to
浏览 1提问于2012-12-24得票数 0
假设我有一个这样的表达式：
(E1)或(e2))和(e3或(e5和e6))和(e7))或(e8))
我需要以表达式列表(e1、e2、e3等)结束，后跟and/or运算符，以便从左到右计算该列表会产生相同的逻辑布尔答案。
ie e1或e2和e5以及e6或e3和e7或e8。但这不是正确的答案，但这是我最终需要解决的问题。
我知道递归下降解析器将计算表达式，但这不是我需要的，我需要得到一个表达式列表，该列表可以在以后从左到右进行计算。
我想把它放在一个二叉树中，然后导航到树的后缀或类似的东西，但这似乎是不正确的。
我曾经足够聪明，能够理解这样的事情，但现在我有了一个孩子，失去了我所有的高级认知能力。
浏览 1提问于2010-01-26得票数 2
1回答
将C程序从使用数组改为使用链表
、、、、
我是一个C的初学者，我已经写了一个‘中缀，前缀，后缀转换’程序使用数组。但是现在我想把程序改成使用链表来说明堆栈。
有没有人可以帮我修改这一小部分代码来使用链表，这样我就可以看到这个模式并理解它是如何工作的？谢谢。
这是‘前缀到中缀转换’的代码
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
char PrefixToInfix(char expression[]){
char *input,ans[50],answer[50][50],opr[3],temp[5]; //Initi
浏览 3提问于2016-12-23得票数 0
当接受像(10+5*15)这样的表达式并遵循操作顺序时。
怎样才能最好地解决这样的问题呢？哪种数据结构是最好的？
谢谢。
浏览 1提问于2011-04-21得票数 5
回答已采纳
2回答
我有一个简单的问题:哪种数据结构是堆栈？它是静态的还是动态的数据结构？我在寻找答案，却找不到答案，所以我有自己的“解释”--我想，当你可以用数组或链表来实现它时，它可以是.两者都是？，取决于实现？我的推理有意义吗？
浏览 5提问于2016-01-21得票数 2
回答已采纳
7回答
在使用C++或C#时，有没有办法将反向波兰语表示法解释为“正常”数学表示法？我在一家工程公司工作，所以他们偶尔会使用RPN，我们需要一种方法来转换它。有什么建议吗？
浏览 1提问于2008-09-22得票数 9
回答已采纳
1回答
一个很奇怪的问题，但是有没有可能重载某些括号类型的含义，比如Python语言中的<, >, [, ] and |。例如，如果我有一些对象实例MyObj1和MyObj2，我可以设计一些东西来将<MyObj1 | MyObj2 >理解为MyObj1中的一个方法调用吗
我认为这可能不能/不应该做，但我想我应该问一下！
浏览 1提问于2015-01-23得票数 1
1回答
有必要记住数据结构的代码吗？
、、、、
是否需要记住链表、动态数组、循环链表、队列、堆栈、图形等数据结构的代码，或者仅仅是对代码的基本知识就足够了？关于数据结构，在面试中可以问到什么样的问题？
浏览 3提问于2020-10-03得票数 0
回答已采纳
8回答
有没有C“自带”的队列数据结构实现，或者我必须自己开发(这是为了一个学校项目，因此我必须使用标准的gcc安装中存在的东西，或者必须自己实现一个！)
其他通用的数据结构，如链表、堆栈等呢？
浏览 0提问于2010-11-15得票数 11
回答已采纳
4回答
我有下面的链表结构：
struct Node {
int type;
int otherInfo;
Node * next;
}
我想创建一个排序的(最终)链表，跟踪每个"type“出现的次数。示例节点为：
struct Node2 {
int type;
int frequency;
//A linked list to keep track of the "otherInfo"
Node2 * next;
}
我目前的算法是O(n^2)，这是不合理的，因为原始链表有时可以有超过30,000个元素。有没有更有效的
浏览 0提问于2011-04-17得票数 0
回答已采纳
2回答
我知道像数组，链表之类的东西是数据structures...but对象呢？
比如，如果我创建了一个对象，比如employee，它会存储并跟踪员工的姓名、薪水、电话number...etc等。
浏览 3提问于2016-02-03得票数 1
4回答
在使用Scala编程时，我会做越来越多的函数式工作。但是，在使用中缀表示法时，很难区分什么时候需要括号，什么时候不需要。
例如，下面这段代码：
def caesar(k:Int)(c:Char) = c match {
case c if c isLower => ('a'+((c-'a'+k)%26)).toChar
case c if c isUpper => ('A'+((c-'A'+k)%26)).toChar
case _ => c
}
def encrypt(file:Str
浏览 2提问于2011-04-08得票数 15
回答已采纳
2回答
链接列表是否被视为对象的集合？
、、、、
塞奇威克算法4ed说
几种基本数据类型涉及对象的集合。具体来说，值集是对象的集合，操作主要围绕在集合中添加、删除或检查对象。在本节中，我们将考虑三种这样的数据类型，即包、队列和堆栈。它们在接下来要移除或检查哪个对象的规范上有所不同。..。链接列表是一个递归数据结构，它要么是空的(null)，要么是对具有泛型项的节点的引用，或者是对链接列表的引用。
在一般的编程语言理论中，还是仅仅在Java语言或库中，“集合”的概念定义得很好？
链接列表是集合吗？这本书没有说链表是一个集合，而是说这三个集合，即一个袋子，队列和堆栈，可以用链表来实现。但是，链接列表似乎具有集合的一些特性，但我不确定它是否具有集合
浏览 0提问于2016-10-07得票数 3
我有一个简单的函数，我想使用后缀表示法来调用它
import anorm._
class SimpleRepository {
private def run(sql: SimpleSql[Row]) = sql.as(SqlParser.scalar[String].*)
// this is how i'd like to call the method
def getColors(ids: Seq[UUUID])(implicit conn: Connection) = run SQL"""select color from colors w
浏览 4提问于2017-02-28得票数 0
回答已采纳
1回答
我已经成功地在C++中实现了将中缀表达式转换为后缀表达式的分流码数算法。我需要修改我的算法来返回一个前缀(波兰语)表达式，但我不知道怎么做。
infixt(string s) {
infixExpression = s;
string temp;
stack = new Stack();
for (int i = 0; i < infixExpression.length(); i++) {
if (infixExpression[i] != ' ') {
temp += s[i];
} else {
if (isOp
浏览 14提问于2020-11-10得票数 0
我被要求评估一个给定操作的结果。例如，如果给我一个字符串，((6-(2+3))*(3+8/2))^2+3结果应该是52.0000。只给出一个数字(0 -> 9)。这是我的教授在HackerRank上发布的一个自定义问题。我正在使用CodeBlocks，一切都很顺利，但是当我在HackerRank上测试代码时，它给了我一个运行时错误，但在所有测试用例上都显示了正确的输出，所以很明显它被拒绝了。 我重写了代码2次，结果仍然是一样的。我使用的是C语言和堆栈(这是必须的)。请任何人告诉我为什么我得到一个运行时错误！？我仍然是一个菜鸟:p，所以提前为任何明显的错误道歉。 代码如下： #inclu
浏览 26提问于2020-04-10得票数 1
2回答
基于链表的数据结构堆栈具有以下基本指针和顶部指针：
指向堆栈的成员。
struct node
{
struct node* next;
int val;
};
struct stack
{
struct node* base;
struct node* top;
}
所以我的问题是，我们能用同样的方式创建一个链接列表吗？
如果我们想在列表的后面添加新成员，我们不需要
翻阅整个名单。
struct listnode
{
struct listnode* next;
int val;
};
struc
浏览 2提问于2019-03-08得票数 0
回答已采纳
14回答
在我从事编程的10年中，我可以用一只手计算我使用过的数据结构的数量:数组、链表(我将堆栈和队列集中在一起)和字典。这并不奇怪，因为我编写的几乎所有应用程序都属于forms-over-data / CRUD类别。
我从来不需要使用红黑树、跳跃列表、双端队列、循环链表、优先级队列、堆、图或过去50年来研究过的几十种奇异数据结构中的任何一种。我觉得我错过了。
这是一个开放式的问题，但是在实践中这些“奇异”的数据结构在哪里使用呢？有没有人有使用这些数据结构解决特定问题的实际经验？
浏览 4提问于2008-12-23得票数 45
回答已采纳
3回答
为什么我们要使用数组来实现堆栈和队列，而可以用链接列表来完成呢？我刚刚学会了使用链表来实现堆栈和队列，所以从现在开始，自然地使用数组对我来说没有意义，更具体地说，我们可以让O(1) push和pop只操作head指针，而不必担心数组的大小，除非它太大了。
浏览 0提问于2019-08-20得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM活动推荐
腾讯云开发者
