- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C语言数据结构之中缀树转后缀树的实例由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
C语言数据结构之中缀树转后缀树的实例 。
对于一个中缀表达式 a+b*c*(d-e/f) 转换成后缀是这样的形式 abc*def/-+ 。
后缀表达式是相当有用处的,转换成后缀表达式后求值会简单很多.那么该如何转换呢?
网上关于这方面的资料一搜一大把,每本数据结构的书中都会提及这个算法,在这个算法中,用到 栈 这个数据结构. 。
1,关键是比较运算符的优先级,谁的优先级高,谁就出现在前面上面的表达式中,有括号的时候括号优先级最高,*/次之,+-最后. 在上面的表达式中+的优先级不如*的高,因此,在后缀表达式中*出现在+前面.
2,遇到操作数的时候总是直接输出,不做任何比较 。
3,遇到左括号总是直接入栈,遇到右括号的时候总是弹栈,一直弹到遇到一个左括号 。
4,遇到操作符的时候就先将这个操作符和它前面的操作符比较优先级,假如高于前面的优先级,先将它压栈,假如低于或等于前面的操作符的优先级,就把前面的优先级比它高的或相等的顺序弹出来, 一直弹到遇到优先级比它还低的或者到了栈顶 ,然后该操作符再压入栈.
知道以上四个规则就可以设计代码实现了, 。
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
#include<iostream>
#include<string>
#include<stack>
#include<map>
using namespace std;
void
InerStringDevide(string InerStr,string DeviStr[],
int
&num)
{
int
count,i;
int
numbe=InerStr.size();
for
(i=
0
;i<numbe;i++)
DeviStr[i][
0
]=
'\0'
;
count=
0
;
for
(i=
0
;i<numbe;)
{
if
(InerStr[i]==
'+'
||InerStr[i]==
'-'
||InerStr[i]==
'*'
||
InerStr[i]==
'/'
||InerStr[i]==
'%'
||InerStr[i]==
'^'
||InerStr[i]==
'('
||InerStr[i]==
')'
)
{
DeviStr[count].push_back(InerStr[i]);
count++;
i++;
}
else
{
while
(InerStr[i]!=
'+'
&&InerStr[i]!=
'-'
&&InerStr[i]!=
'*'
&&
InerStr[i]!=
'/'
&&InerStr[i]!=
'%'
&&InerStr[i]!=
'^'
&&InerStr[i]!=
'('
&&InerStr[i]!=
')'
)
{
DeviStr[count].push_back(InerStr[i]);
i++;
if
(i>=numbe)
break
;
}
count++;
}
}
num=count;
}
void
InerTreeToPostTree(string InerStr,string &PostStr)
{
PostStr[
0
]=
'\0'
;
map<
char
,
int
>OpC;
typedef map<
char
,
int
>::value_type ValType;
OpC.insert(ValType(
'+'
,
1
));
OpC.insert(ValType(
'-'
,
1
));
OpC.insert(ValType(
'*'
,
2
));
OpC.insert(ValType(
'/'
,
2
));
OpC.insert(ValType(
'%'
,
2
));
OpC.insert(ValType(
'^'
,
3
));
OpC.insert(ValType(
'('
,-
1
));
OpC.insert(ValType(
')'
,
0
));
int
num,i,j,StrNum;
num=InerStr.size();
string *DevedeStr=
new
string[num];
InerStringDevide(InerStr,DevedeStr,StrNum);
stack<
char
> ChStack;
int
count=
0
;
for
(
int
i=
0
;i<StrNum;i++)
{
//如果输入的字符串是操作符
if
(DevedeStr[i][
0
]==
'+'
||DevedeStr[i][
0
]==
'-'
||DevedeStr[i][
0
]==
'*'
||
DevedeStr[i][
0
]==
'/'
||DevedeStr[i][
0
]==
'%'
||DevedeStr[i][
0
]==
'^'
||DevedeStr[i][
0
]==
'('
||DevedeStr[i][
0
]==
')'
)
{
//如果操作符栈中为空可以直接将操作符入栈
if
(ChStack.empty())
{
ChStack.push(DevedeStr[i][
0
]);
}
//如果非空要根据操作符的优先级及其类别进行判断并分类入栈
else
{
char
TopCh=ChStack.top();
//如果是(则直接入栈
if
(OpC[DevedeStr[i][
0
]]==-
1
)
{
ChStack.push(DevedeStr[i][
0
]);
}
//如果操作符优先级大于栈中当前操作符直接入栈
else
if
(OpC[TopCh]<OpC[DevedeStr[i][
0
]])
{
ChStack.push(DevedeStr[i][
0
]);
}
//否则按操作符的类别有区别的处理
else
{
//如果遇到)则操作符出栈并入字符串
if
(OpC[DevedeStr[i][
0
]]==
0
)
{
TopCh=ChStack.top();
while
(OpC[TopCh]!=-
1
)
{
if
(!PostStr.empty())
{
PostStr.push_back(
' '
);
}
PostStr.push_back(TopCh);
ChStack.pop();
TopCh=ChStack.top();
}
ChStack.pop();
TopCh=ChStack.top();
}
else
{
while
(OpC[TopCh]>=OpC[DevedeStr[i][
0
]]&&OpC[TopCh]!=-
1
)
{
if
(!PostStr.empty())
{
PostStr.push_back(
' '
);
}
PostStr.push_back(TopCh);
ChStack.pop();
if
(!ChStack.empty())
TopCh=ChStack.top();
else
break
;
}
ChStack.push(DevedeStr[i][
0
]);
}
}
}
}
//如果输入的字符串是数字
else
{
int
DevideSize=DevedeStr[i].size();
if
(!PostStr.empty())
{
PostStr.push_back(
' '
);
}
for
(
int
j=
0
;j<DevideSize;j++)
{
PostStr.push_back(DevedeStr[i][j]);
}
}
}
while
(!ChStack.empty())
{
if
(!PostStr.empty())
{
PostStr.push_back(
' '
);
}
PostStr.push_back(ChStack.top());
ChStack.pop();
}
}
|
以上为头文件InerTreeToPostTree.h。该文件的 作用是输入中缀字符串,输出后缀字符串,其中中缀字符串不带空格,而后缀字符串带空格。头文件中的另一个函数是将字符串分为字符串数组,该数组中存储数字和运算符.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#include<iostream>
#include<stack>
#include<string>
using
namespace
std;
void
StringDevide(string str,
int
&num,string st1[])
{
for
(
int
i=0;i<100;i++)
st1[i][0]=
'\0'
;
int
n=str.size();
int
j=0,count=0;
for
(
int
i=0;i<n;i++)
{
if
(str[i]!=
' '
)
{
st1[count].push_back(str[i]);
}
else
{
count++;
}
}
num=count+1;
}
void
StringToNum(string str,
int
&num)
{
num=0;
int
n=str.size();
for
(
int
i=0;i<n;i++)
{
num=num*10;
num+=str[i]-
'0'
;
}
}
class
InterTreeComputer
{
private
:
//要计算的表达式
string m_expresion;
//将数字存储到栈中
stack<
int
> m_num;
public
:
InterTreeComputer(string expression):m_expresion(expression)
{}
//判定某一操作符是否是运算符
bool
IsOperator(
char
ch)
const
;
//获取要计算的两个运算数
void
GetOperands(
int
&left,
int
&right);
//对获取的两个数按照符号ch进行计算
int
computer(
int
left,
int
right,
char
ch)
const
;
//获取表达式
string GetPostoperation()
const
;
void
SetPostoperator();
//计算表达式并返回结果
int
Evaluate();
};
bool
InterTreeComputer::IsOperator(
char
ch)
const
{
switch
(ch)
{
case
'+'
:
case
'-'
:
case
'*'
:
case
'/'
:
case
'%'
:
case
'^'
:
return
1;
default
:
return
0;
}
}
void
InterTreeComputer::GetOperands(
int
&left,
int
&right)
{
if
(m_num.empty())
{
cout<<
"num stack is empty!"
;
return
;
}
right=m_num.top();
m_num.pop();
if
(m_num.empty())
{
cout<<
"the expression is wrong!"
<<endl;
return
;
}
left=m_num.top();
m_num.pop();
}
int
InterTreeComputer::computer(
int
left,
int
right,
char
ch)
const
{
switch
(ch)
{
case
'+'
:
return
left+right;
break
;
case
'-'
:
return
left-right;
break
;
case
'*'
:
return
left*right;
break
;
case
'/'
:
if
(right==0)
{
cout<<
"the expression is wrong"
<<endl;
return
-1;
}
return
left/right;
break
;
case
'%'
:
return
left%right;
break
;
case
'^'
:
if
(left==0&&right==0)
{
cout<<
"the expression is wrong"
<<endl;
return
-1;
}
int
value=1;
while
(right>0)
{
value*=left;
right--;
}
return
value;
break
;
}
}
string InterTreeComputer::GetPostoperation()
const
{
return
m_expresion;
}
void
InterTreeComputer::SetPostoperator()
{}
int
InterTreeComputer::Evaluate()
{
string *str=
new
string[100];
int
num;
StringDevide(m_expresion,num,str);
for
(
int
i=0;i<num;i++)
{
if
(str[i][0]==
'+'
||str[i][0]==
'-'
||str[i][0]==
'*'
||str[i][0]==
'/'
||str[i][0]==
'%'
||str[i][0]==
'^'
)
{
char
ch=str[i][0];
int
left,right;
GetOperands(left,right);
int
number=computer(left,right,ch);
m_num.push(number);
}
else
{
int
numb=0;
StringToNum(str[i],numb);
m_num.push(numb);
}
}
return
m_num.top();
}
|
以上代码为InerTreeComputer.h头文件,该头文件的作用是输入后缀表达式并计算该表达式的值.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include<iostream>
using
namespace
std;
#include<string>
#include<stack>
#include"InterTreeComputer.h"
#include"InerTreeToPostTree.h"
int
main()
{
string str=
"3*(4-2^5)+6"
;
string st1=
"2 3 ^ 1 +"
;
string st2=
"2 2 3 ^ ^ 4 /"
;
string StrRe;
InerTreeToPostTree(str,StrRe);
InterTreeComputer Comp(StrRe);
cout<<Comp.GetPostoperation()<<endl;
cout<<Comp.Evaluate()<<endl;
return
0;
}
|
测试文件对以上两个头文件进行了测试.
以上就是数据结构C语言数据结构之中缀树转后缀树的实例,如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持,大家共同进步! 。
原文链接:http://blog.csdn.net/liuzhanchen1987/article/details/7387480 。
最后此篇关于C语言数据结构之中缀树转后缀树的实例的文章就讲到这里了,如果你想了解更多关于C语言数据结构之中缀树转后缀树的实例的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
有没有一种方法可以使用标准类型构造函数(例如 int、set、dict、list、tuple 等)以用户定义的方式将用户定义类的实例强制转换为其中一种类型?例如 class Example:
我知道这个问题在Stackoverflow中有很多问题,但是即使有很多答案,这些答案也帮不了我什么,也没有找到答案。 在我的WebAPP中,它可以正常工作,但是当我将其转换为API时,它失败了(主题标
这个问题已经有答案了: Why does the ternary operator unexpectedly cast integers? (3 个回答) 已关闭 9 年前。 最近遇到一个Java的陷
我尝试使用 FirebaseApp.configure() 配置 Firebase,但遇到以下崩溃: *** Terminating app due to uncaught exception 'c
我有一个自连接员工实体类,其中包含与其自身相关的 id、name 和 ref 列。我想创建它的新实例并将其保存到数据库。 首先我创建了一个 Employee 类的实例并将其命名为 manager。然后
我有一个用于添加新公寓的表单,在该表单中我有一个下拉列表,用户可以在其中选择负责的人员。 显然,当您从下拉列表中选择并尝试保存公寓时,我的应用程序认为该人已被修改。它给了我下面的错误,指示我应该首先保
从 Visualforce 页面,我需要检索我们组织的 salesforce 实例的 URL,而不是 Visual Force URL。 例如我需要https://cs1.salesforce.com
我遇到了一些可能的问题答案,但这是关于从 Hibernate 3.4.0GA 升级到 Hibernate 4.1.8 的问题。所以这曾经在以前的版本下工作,我已经四处搜索了为什么它在这个新版本中出现了
似乎一遍又一遍地问这个问题,我仍然找不到解决我问题的答案。我在下面有一个域模型。每个新创建或更新的“安全用户”都需要我确保其具有配置文件,如果没有,则创建一个新的配置文件并分配给它。 配置文件的要求相
我很难调试为什么 JPA 不级联我的 @ManyToMany 关系。我发现的所有答案都与缺少级联语句有关。但我确实拥有它们并且仍然得到: Caused by: org.hibernate.Transi
Play 服务 API 表明有一个叫做 Instance ID 的东西 但是,在 Android Studio 中包含以下内容后,我无法导入 InstanceID 类 compile "com.goo
我正在使用 Seam 框架。我有 2 个实体: 请求.java @Entity @Table(name = "SRV_REQUEST") public class Request { private
This question处理构建一个适当的Monad来自单子(monad)的实例,但仅在某些约束下 - 例如Set .诀窍是将其包装成 ContT ,它将约束推迟到包装/展开其值。 现在我想对 Ap
我正在尝试执行此查询: StringBuffer sb = new StringBuffer(); sb.append("select p from PointsEntity p " + "where
我试图了解是否可以更改我的 hibernate 配置并使用单个 MySQL 实例(而不是我当前拥有的多个 MySQL 实例): 我有一个使用 hibernate 的 Java 应用程序,与 2 个模式
我有一个选项卡滑动布局,其中包括四个选项卡,每个选项卡都有自己的布局和 fragment ,在我的主要 Activity 布局中,viewpager 参与更改选项卡。特定 View (选项卡)在应用程
我看到很多帖子声称他们正在运行 MySql 的 RDS 实例,但无法连接到该实例,但我没有运行 RDS。 我使用 EC2 实例来托管我的 WordPress 博客,该博客是使用 Web 平台安装程序安
因为我在我的 ec-2 实例上的 python 虚拟环境中运行应用程序( Airflow ),并且我想在同一个 ec2 实例上的默认 python 环境中运行命令,所以我认为 ssh 到我自己的实例更
这个问题已经有答案了: How to fix the Hibernate "object references an unsaved transient instance - save the tra
例子: run APP1 .. ... run APP1 ... run APP2 如何在 APP2 中对 Vue 说我需要调用 APP1?
我是一名优秀的程序员,十分优秀!