当前位置:网站首页>Detailed idea and code implementation of infix expression to suffix expression
Detailed idea and code implementation of infix expression to suffix expression
2022-07-06 19:09:00 【Wu Yu 4】
What is infix expression ?
Infix expression is a general expression of arithmetic or logic formula , Operators are in the middle of operands in the form of infixes (eg:3+4、3+4*2、8+(17-6*2)….).
Why do you want infix expression to suffix expression ?
But infix expressions are not easy to be processed by computers . We are calculating an equation ( Usually infix expression ) when , You need to convert infix expression into suffix expression .
What is a suffix expression ?
Then the suffix expression , Also known as reverse Polish , Does not contain brackets , The operator is placed after two operands , All calculations are in the order in which the operators appear , Strictly from left to right ( The precedence rules for operators are no longer considered ). Generally, stack is used to simulate .
How to convert infix expression into suffix expression ?
Take a simple chestnut :
(3+4)×5-2
Draw a tree like this :
So the suffix expression is :
3 4 + 5 × 2 -
The following is the idea of transformation :
1. Initialize two character array simulation stacks : Character storage stack s1 And a stack for storing intermediate results s2;
2. Scan infix expressions from left to right ;
3. When it comes to operands , Press it down s2;
4. When an operator is encountered , Compare it with s1 The priority of the top of stack operator :
If s1 It's empty , Or stack top operator is left bracket “(”, This operator will be put on the stack directly ;
otherwise , If the priority is higher than the top of the stack operator , Also push operators into s1;
otherwise , take s1 The operator at the top of the stack pops up and pushes into s2 in , Turn again ① And s1 Compared with the new stack top operators in ;
5. When brackets are encountered :
If it's left parenthesis “(”, Press in directly s1;
If it's right bracket “)”, Then it pops up in turn s1 The operator at the top of the stack , And press in s2, Until we meet the left bracket , This pair of parentheses is discarded ;
6. Repeat step 2 to 5, Up to the far right of the expression ;
7. take s1 The rest of the operators in the pop-up and press in s2;
8. Pop up one by one s2 And output , The reverse order of the result is the suffix expression corresponding to the infix expression
Then it can be calculated according to the suffix expression .
Be sure to pay attention to the calculation order of taking out elements ! The number taken out first is
X
Count
(X To reduce / except / Add / ride ), The number taken out after isBy
X
Count
!
Code ( There are detailed notes ):
#include<bits/stdc++.h>// Universal header file
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);// Accelerated statement
typedef long long ll;
const int N=1e5+10;
char s1[N],s2[N],s[N];
ll top1,top2,p,js[N],topis;
int lev(char n)
{
if(n=='+'||n=='-') return 1;
if(n=='*'||n=='/') return 2;
if(n=='^') return 3;
return 0;
}
void print()
{
for(int i=1;i<=topis;i++)// Currently being calculated
{
cout<<js[i]<<' ';
}
for(int i=p+1;i<=top2;i++)// Not traversed later
{
cout<<s2[i];
if(i!=top2)
cout<<" ";
}
if(p!=top2)
cout<<endl;
}
int main()
{
cin>>s;
for(int i=0;i<strlen(s);i++)
{
if(s[i]<='9'&&s[i]>='0')
{
s2[++top2]=s[i];
}
else
{
if(s[i]=='(')
{
s1[++top1]=s[i];
continue;
}
if(s1[top1]=='('||top1==0)
{
s1[++top1]=s[i];
continue;
}
if(lev(s1[top1])>=lev(s[i])&&s[i]!=')')// When it comes in, it's not the right bracket , And the incoming symbol priority has no s1 The stack top symbol of has high priority
// At this time, we need to s1 The top element of the stack is given to s2 in
{
s2[++top2]=s1[top1--];
while(lev(s1[top1])>=lev(s[i]))// If the priority level is still not as high as the symbol to enter , Continue to give s2 in
{
s2[++top2]=s1[top1--];
}
// At the end of the cycle , There is no symbol priority to enter s1 The stack top symbol of has high priority , You can deposit s1 in
s1[++top1]=s[i];
continue;
}
if(lev(s1[top1])<lev(s[i])&&s[i]!=')')
{
s1[++top1]=s[i];
}
if(s[i]==')')// Yes ' ) '
{
while(s1[top1]!='(')// take s1 The symbols in are given to s2 in , Until I met ' ) '
{
s2[++top2]=s1[top1--];
}
top1--;
continue;
}
}
}
while(top1>0)// if s1 And symbols , Need to give s2 in
{
s2[++top2]=s1[top1--];
}
for(int i=1;i<=top2;i++)
{
cout<<s2[i]<<" ";
}
cout<<endl;
// Perfect infix to suffix
// Next, calculate
for(int i=1;i<=top2;i++)
{
p=i;
if(s2[i]>='0'&&s2[i]<='9')
{
js[++topis]=s2[i]-'0';
}
else // For the sign , Operate on the two elements at the top of the stack , And store the results on the top of the stack
{
// Pay attention to the first digit of the advanced stack
if(s2[i]=='+')
{
ll x=js[topis];
ll y=js[--topis];
ll ans=y+x;
js[topis]=ans;
}
if(s2[i]=='-')
{
ll x=js[topis];
ll y=js[--topis];
ll ans=y-x;
js[topis]=ans;
}
if(s2[i]=='*')
{
ll x=js[topis];
ll y=js[--topis];
ll ans=y*x;
js[topis]=ans;
}
if(s2[i]=='/')
{
ll x=js[topis];
ll y=js[--topis];
ll ans=y/x;
js[topis]=ans;
}
if(s2[i]=='^')
{
ll x=js[topis];
ll y=js[--topis];
ll ans=pow(y,x);
js[topis]=ans;
}
print();// Print every step
}
}
return 0;
}
The operation results are as follows :
边栏推荐
- AcWing 3537.树查找 完全二叉树
- pytorch常见损失函数
- Unlock 2 live broadcast themes in advance! Today, I will teach you how to complete software package integration Issues 29-30
- Certains marchés de l'emploi de Shanghai refusent d'embaucher des personnes qui se rétablissent positives à Xinguan
- Graffiti intelligence is listed on the dual main board in Hong Kong: market value of 11.2 billion Hong Kong, with an annual revenue of 300 million US dollars
- Lucun smart sprint technology innovation board: annual revenue of 400million, proposed to raise 700million
- Actf 2022 came to a successful conclusion, and 0ops team won the second consecutive championship!!
- 上海部分招工市场对新冠阳性康复者拒绝招录
- QLabel 跑马灯文字显示
- Intelligent supply chain management system solution for hardware and electromechanical industry: digital intelligent supply chain "creates new blood" for traditional industries
猜你喜欢
How word displays modification traces
Interface test tool - postman
ORACLE进阶(四)表连接讲解
Reptiles have a good time. Are you full? These three bottom lines must not be touched!
美庐生物IPO被终止:年营收3.85亿 陈林为实控人
【论文笔记】TransUNet: Transformers Make StrongEncoders for Medical Image Segmentation
提前解锁 2 大直播主题!今天手把手教你如何完成软件包集成?|第 29-30 期
二叉搜索树
RT-Thread 组件 FinSH 使用时遇到的问题
中缀表达式转后缀表达式详细思路及代码实现
随机推荐
QLabel 跑马灯文字显示
Installation and management procedures
Human bone point detection: top-down (part of the theory)
Solve DoS attack production cases
基于ppg和fft神经网络的光学血压估计【翻译】
Synchronous development of business and application: strategic suggestions for application modernization
使用map函数、split函数一行键入多个元素
The nearest library of Qinglong panel
R language ggplot2 visualization: use the ggdotplot function of ggpubr package to visualize dot plot, set the palette parameter, and set the colors of data points and box graphs of dot plots at differ
wx小程序学习笔记day01
快速幂模板求逆元,逆元的作用以及例题【第20届上海大学程序设计联赛夏季赛】排列计数
Lucun smart sprint technology innovation board: annual revenue of 400million, proposed to raise 700million
如何提高网站权重
Mathematics in machine learning -- common probability distribution (XIII): Logistic Distribution
数学知识——高斯消元(初等行变换解方程组)代码实现
第五期个人能力认证考核通过名单公布
Pychrm Community Edition calls matplotlib pyplot. Solution of imshow() function image not popping up
根据PPG估算血压利用频谱谱-时间深度神经网络【翻】
Take a look at how cabloyjs workflow engine implements activiti boundary events
Video based full link Intelligent Cloud? This article explains in detail what Alibaba cloud video cloud "intelligent media production" is