使用栈数据结构将中缀表达式转换为后缀表达式的 C++ 程序

17 Mar 2025 | 4 分钟阅读

中缀表达式

中缀表达式是一种运算符（+、-、*、/）写在两个操作数之间的表达式。例如，考虑以下表达式

A + B
A + B - C
(A + B) + (C - D)

这里我们将运算符 '+' 写在操作数 A 和 B 之间，将运算符 - 写在操作数 C 和 D 之间。

后缀表达式

后缀表达式也包含运算符和操作数。在后缀表达式中，运算符写在操作数之后。它也被称为 逆波兰表示法。例如，考虑以下表达式

A B +   
A B + C -   
A B C * +
A B + C * D -

使用栈将中缀表达式转换为后缀表达式的算法

以下是将中缀表达式转换为逆波兰表示法的算法。

初始化栈。
从左到右扫描中缀表达式中的运算符。
如果最左边的字符是操作数，则将其设置为后缀字符串的当前输出。
如果扫描到的字符是运算符且栈为空或包含 '('、')' 符号，则将运算符推入栈中。
如果扫描到的运算符的优先级高于栈中现有运算符的 优先级，或者栈为空，则将其推入栈中。
如果扫描到的运算符的优先级低于栈中现有运算符的优先级，则弹出所有栈中的运算符。之后，将扫描到的运算符推入栈中。
如果扫描到的字符是左括号 '('，则将其推入栈中。
如果遇到右括号 ')'，则弹出栈并打印所有输出字符串字符，直到遇到 '('，并丢弃两个括号。
重复步骤 2 到 8，直到中缀表达式扫描完毕。
打印栈输出。
从栈中弹出并输出所有字符，包括运算符，直到栈为空。

让我们将中缀表达式转换为栈中的后缀表达式

这里，我们有中缀表达式 (( A * (B + D)/E) - F * (G + H / K))) 要转换为等效的后缀表达式

标签编号。	扫描到的符号	Stack	表达
1	(	(
2	(	((
3	A	((	A
4	*	((*	A
5	(	((*(	A
6	B	((*(	AB
7	+	((*(+	AB
8	D	((*(+	ABD
9	)	((*	ABD+
10	/	((*/	ABD+
11	E	((*/	ABD+E
12	)	(	ABD+E/*
13	-	(-	ABD+E/*
14	(	(-(	ABD+E/*
15	F	(-(	ABD+E/*F
16	*	(-(*	ABD+E/*F
17	(	(-(*(	ABD+E/*F
18	G	(-(*(	ABD+E/*FG
19	+	(-(*(+	ABD+E/*FG
20	H	(-(*(+	ABD+E/*FGH
21	/	(-(*(+/	ABD+E/*FGH
22	K	(-(*(+/	ABD+E/*FGHK
23	)	(-(*	ABD+E/*FGHK/+
24	)	(-	ABD+E/FGHK/+
25	)		ABD+E/FGHK/+-

将中缀表达式转换为后缀表达式的程序

让我们创建一个 C++ 程序，将中缀表达式转换为后缀表达式

#include<iostream>
#include<stack>
using namespace std;
// defines the Boolean function for operator, operand, equalOrhigher precedence and the string conversion function.
bool IsOperator(char);
bool IsOperand(char);
bool eqlOrhigher(char, char);
string convert(string);

int main()
{
string infix_expression, postfix_expression;
int ch;
do
{
cout << " Enter an infix expression: ";
cin >> infix_expression;
 postfix_expression = convert(infix_expression);
 cout << "\n Your Infix expression is: " << infix_expression;
cout << "\n Postfix expression is: " << postfix_expression;
cout << "\n \t Do you want to enter infix expression (1/ 0)?";
cin >> ch;
//cin.ignore(); 
} while(ch == 1);
return 0;
}

// define the IsOperator() function to validate whether any symbol is operator.
/* If the symbol is operator, it returns true, otherwise false. */
bool IsOperator(char c)
{
if(c == '+' || c == '-' || c == '*' || c == '/' || c == '^' )
return true;   
return false;
}

// IsOperand() function is used to validate whether the character is operand.
bool IsOperand(char c)
{
if( c >= 'A' && c <= 'Z')  /* Define the character in between A to Z. If not, it returns False.*/
return true;
if (c >= 'a' && c <= 'z')  // Define the character in between a to z. If not, it returns False. */
return true;
if(c >= '0' && c <= '9')   // Define the character in between 0 to 9. If not, it returns False. */
return true;
return false;
}
// here, precedence() function is used to define the precedence to the operator.
int precedence(char op)
{
if(op == '+' || op == '-')                   /* it defines the lowest precedence */
return 1;
if (op == '*' || op == '/')
return 2;
if(op == '^')                                  /* exponent operator has the highest precedence *
return 3;      
return 0;
}
/* The eqlOrhigher() function is used to check the higher or equal precedence of the two operators in infix expression. */
bool eqlOrhigher (char op1, char op2)
{
int p1 = precedence(op1);
int p2 = precedence(op2);
if (p1 == p2)
{
if (op1 == '^' )
return false;
return true;
}
return  (p1>p2 ? true : false);
}

/* string convert() function is used to convert the infix expression to the postfix expression of the Stack */
string convert(string infix)
{
stack <char> S;
string postfix ="";  
char ch;

S.push( '(' );
infix += ')';

for(int i = 0; i<infix.length(); i++)
{
ch = infix[i];

if(ch == ' ')
continue;
else if(ch == '(')
S.push(ch);
else if(IsOperand(ch))
postfix += ch;
else if(IsOperator(ch))
{
while(!S.empty() && eqlOrhigher(S.top(), ch))
{
postfix += S.top();
S.pop();
}
S.push(ch);
}
else if(ch == ')')
{
while(!S.empty() && S.top() != '(')
{
postfix += S.top();
S.pop();
}
S.pop();
}
}
return postfix;
}

输出

Program to convert infix to postfix expression in C++ using the Stack Data Structure

下一主题C++ 程序合并两个未排序数组

使用栈数据结构将中缀表达式转换为后缀表达式的 C++ 程序

中缀表达式

后缀表达式

使用栈将中缀表达式转换为后缀表达式的算法

将中缀表达式转换为后缀表达式的程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

使用栈数据结构将中缀表达式转换为后缀表达式的 C++ 程序

中缀表达式

后缀表达式

使用栈将中缀表达式转换为后缀表达式的算法

将中缀表达式转换为后缀表达式的程序

相关帖子

C++ 命名约定

C++ 静态成员

C++ unordered_multimap key_eq 函数

C++ 范围外异常

C++ 对象创建

C++ 打印数字三角形程序

如何创建和使用 CComPtr 和 CComQIPtr 实例

使用 C++ 克隆具有 next 和 Random 指针的链表

C++ 静态成员函数

C++ Boost 库

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器