回文判断
我们把正读和反读都相同的字符序列称为“回文”，例如abba和abcba是回文，abcde不是回文。尝试写一个算法判别读入的一个以@为结束符的字符是否是回文。
输入格式
输入为一行，为待判断的字符串，以@结尾。字符串长度不超过 30，除最后一个字符外，其余字符均由小写字母组成。
输出格式
输出一行，如果输入的字符串是回文，则输出true；如果输入的字符串不是回文，则输出false。
实现代码
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
| #include<iostream>
#include<stdlib.h>
#include<string>
using namespace std;
typedef struct
{
char data[31];
int top;
}sqstack,*sqslink;
bool push(sqslink &s,char x)
{
if(s->top >=30) return 0;
else
{
s->top++;
s->data[s->top]=x;
return 1;
}
}
bool emptystack(sqslink s)
{
if(s->top <0) return 1;
else return 0;
}
char pop(sqslink &s)
{
if(emptystack(s)) return 0;
else
{
s->top--;
return(s->data[s->top]);
}
}
int main()
{
string ch;
sqslink s1,s2;
s1=(sqslink)malloc(sizeof(sqstack));
s2=(sqslink)malloc(sizeof(sqstack));
s1->top =0;
s2->top =0;
cin>>ch;
for(int i=0;i<ch.length()-1;++i)
push(s1,ch[i]);
s1->top+=1;
while(s1->top>1)
{
push(s2,pop(s1));
}
int n=s2->top;
s2->top=n+1;
s1->top=n+1;
for(int i=1;i<=n;++i)
{
if(pop(s1)!=pop(s2))
{
cout<<"false";
return 0;
}
}
cout<<"true";
return 0;
}
|
啊，调试用的输出语句就不删了。
逆波兰式
假设表达式由数字和双目四则运算符+，-，*，/构成。试利用栈实现一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式（后缀表达式），同时将转换后的逆波兰式求值，最后仅需输出求值结果。
输入格式
输入共有一行，为待求值的表达式，以换行结束。表达式保证是合法的，表达式中的整数在 [0,9] 以内，表达式长度不超过 20。表达式中仅包含+，-，*，/以及数字，不会出现其他字符。
输出格式
输出仅有一行，为输入表达式的正确计算结果。
实现代码
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
| #include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;
typedef struct
{
int data[21];
int top;
}sqstack,*sqslink;
int pop(sqslink &s)
{
s->top--;
return s->data[s->top+1];
}
void push(sqslink &s,int x)
{
s->top++;
s->data[s->top]=x;
}
int main()
{
string str;
cin>>str;
sqslink s;
s=(sqslink)malloc(sizeof(sqstack));
s->top=0;
int len=str.length();
bool l=0;
for(int i=0;i<len;++i)
{
if(l)
{
push(s,0-((int)str[i]-48));
l=0;
continue;
}
if(str[i]>=48&&str[i]<=57)
push(s,(int)str[i]-48);
else
if(str[i]=='-')
{
l=1;
continue;
}
else
if(str[i]=='*')
{
push(s,(int)pop(s)*((int)str[i+1]-48));
i++;
}
else
if(str[i]=='/')
{
push(s,(int)pop(s)/((int)str[i+1]-48));
i++;
}
}
while(1)
{
if(s->top<=1) break;
push(s,pop(s)+pop(s));
}
cout<<pop(s);
return 0;
}
|
大概思路就是把该乘除的都算好再存到栈里，最后取出来累加就好了，如果有减号就提前加个负号。
