C++大作业 题目一、二
原创
题目一：请你设计一个算法，从顺序表中删除自第 i 个结点开始的 k 个结点。要求先输出整个顺序表，再输出删除自第 i 个结点开始的 k 个结点后的结果。（ 2022/11/21 ）
【编程提示】 假设 a[max]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; i=5;k=5; 输出结果为： 原顺序表：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 删除结点后：1,2,3,4,10,11,12,13,14,15
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void print(const vector<int> &p);
void test01();
int main() {
test01();
system("pause");
return 0;
}
void print(const vector<int> &p) {
for (vector<int>::const_iterator i = p.begin(); i != p.end(); i++) {
cout << *i << " ";
}
cout << endl;
}
void test01() {
vector<int> v;
for (int i = 1; i <= 15; i++) {
v.push_back(i);
}
cout << "原顺序表：" << endl;
print(v);
cout << "自__开始删除__个节点：" << endl;
int i = 0, k = 0;
cin >> i >> k;
v.erase(v.begin() + i - 1, v.begin() + i + k - 1);
cout << "删除节点后：" << endl;
print(v);
}题目二：请你运用数据结构中“栈”的思想，编写一个算法，要求把输入的中缀表达式转换成后缀表达式，并计算该表达式的值。
【编程提示】
- 用户在键盘上输入表达式时，通常是运算符位于两个操作数之间，即为中缀表达式。 例如：3*(8+4)。计算时遵循“自左向右计算，先乘除后加减，先括号内后括号外”的规则。因此，中缀表达式的计算需要考虑括号、运算符优先级等诸多因素，比较麻烦。而后缀表达式(即波兰表达式)在格式上已经考虑了运算符优先级，消除了括号，运算时只需处理操作数和运算符，比较简洁。
- 该问题可分成两个部分：一个为中缀表达式转换为后缀表达式算法的实现；另一个是对后缀表达式求值。
方法一：
#include<iostream> //万能头文件
#include<stack>
#include <string>
using namespace std;
//#include<bits/stdc++.h> //万能头文件
//using namespace std;
//TypeDe用来判断字符的类型，1表示字母变量，0表示七种运算符
int TypeDe(char c) {
if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '(' || c == ')') return 0;
else return 1;
}
//拼接
void Joint(string *v1, string v2, char opn) {
(*v1) = (*v1) + v2 + opn;
return;
}
//运算符等级优先度的量化评价
int lvl(char c) {
switch (c) {
case '(': return 0; //“(”的优先级最低，这样其他运算符就可以直接进栈
case '+': case '-': return 1;
case '*': case '/': return 2;
case '^': return 3;
case ')': return 4;
}
}
//运算符之间的优先级比较
int cmp(char ctop, char cnew) {
int lvl(char);
if (ctop == '^' && cnew == '^') return 0; //特殊情况，文末会说
if (lvl(ctop) >= lvl(cnew)) return 1;
else return 0;
}
void Operation(string &p) {
string s=p;
stack<int>st;
for (int i = 0; i<s.size(); i++) {
if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
int num1 = st.top();
st.pop();
int num2 = st.top();
st.pop();
if (s[i] == '+')st.push(num2 + num1);
if (s[i] == '-')st.push(num2 - num1);
if (s[i] == '*')st.push(num2*num1);
if (s[i] == '/')st.push(num2 / num1);
}
else {
char ch = s[i];
string s2;
char s1[2] = { ch,0 };
s2 = s1;
st.push(stoi(s2));
}
}
cout << st.top();
}
//主程序
int main() {
int n;
cin >> n;
int TypeDe(char);
void Joint(string*, string, char);
int lvl(char);
for (int k = 0; k<n; k++) {
char c=NULL;
stack<char> op; //op是存放运算符的栈
//cout << "此处的空op size:" << op.size() << endl;
stack<string> vrle;//vrle是存放变量或者运算结果的栈
cout << "vrle元素数：" << vrle.size() << endl;
while ( (c = getchar()) != '#' ) {
if (TypeDe(c) == 1) {
//如果是字母变量，直接进栈vrle即可，注意这里会经过一个char->string的过程
string cstr;
cstr = c;
vrle.push(cstr);
cout << "vrle元素数：" << vrle.size() << endl;
}
else if (op.size() && c != '(') {
char op_top;
op_top = op.top();
while (((op_top != '(' && c == ')') || cmp(op_top, c)>0) && op.size()) {
//如果外面的运算符优先级低于op顶部的运算符，就进行一次运算，并且弹栈一次
string s2 = vrle.top();
vrle.pop();
Joint(&vrle.top(), s2, op_top);
op.pop();
if (op.size())
op_top = op.top();
}
if (c != ')') {
op.push(c);
}
if (op.top() == '(')
op.pop();
}
else {
//如果栈空或者是左括号，直接进栈
op.push(c);
}
/*stack<string> vrle1(vrle);
while (vrle1.size()) {
cout << vrle1.top();
vrle1.pop();
}*/
}
//op栈内可能还有未参与运算的运算符
while (op.size()) {
char op_top;
op_top = op.top();
string s2 = vrle.top();
cout << "vrle元素数："<<vrle.size() << endl;
vrle.pop();
cout << "vrle元素数：" << vrle.size() << endl;
Joint(&vrle.top(), s2, op_top);
op.pop();
}
string temp=vrle.top();
//输出
while (vrle.size()) {
cout << vrle.top();
vrle.pop();
}
//cout <<temp <<temp.size()<< endl;
/*string s, temp;
temp = vrle.top();
vrle.pop();
s = vrle.top() + temp;
cout << s << endl;*/ //测试
Operation(temp);
}
system("pause");
return 0;
}值得注意：关于C++字符char为空 即
char a; sizeof(a)=1;
char a=NULL; sizeof(a)=1;
char a='a'; sizeof(a)=1;
慎用getchar(),换用cin.get() 或 cin>> 会好很多，不会造成vrle堆栈的底端无缘无故多出一个’\n'换行符，使得最后的堆栈size=2;
方法二：
/*--------------------------------------------------------------*/
方法2
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int prio(char op) { //给运算符优先级排序
int priority = 0;
if (op == '*' || op == '/')
priority = 2;
if (op == '+' || op == '-')
priority = 1;
if (op == '(')
priority = 0;
return priority;
}
bool Trans(string& str1, string& str2) { //引用传递
stack<char> s; //定义一个char类型的栈s
int i;
for (i = 0; i < str1.size(); i++)
{
if (str1[i] >= '0' && str1[i] <= '9') { //如果是数字，直接入栈
str2 += str1[i];
}
else //否则不是数字
{
if (s.empty()) //栈空则入站
s.push(str1[i]);
else if (str1[i] == '(') //左括号入栈
s.push(str1[i]);
else if (str1[i] == ')') { //如果是右括号，只要栈顶不是左括号，就弹出并输出
while (s.top() != '(') {
str2 += s.top();
s.pop();
}
s.pop(); //弹出左括号，但不输出
}
else { //当栈顶非空时
while (prio(str1[i]) <= prio(s.top())) { //当栈顶优先级大于等于当前运算符，输出
str2 += s.top();
s.pop();
if (s.empty()) //栈为空，停止
break;
}
s.push(str1[i]); //把当前运算符入栈
}
}
}
while (!s.empty()) { //最后，如果栈不空，则弹出所有元素并输出
str2 += s.top();
s.pop();
}
return true;
}
int main() { //主程序
string infix; //保存输入的中缀表达式
string postfix;
cout << "请输入中缀表达式：" << infix << endl;
cin >> infix;
Trans(infix, postfix);
cout << "后缀表达式为：" << postfix << endl;
system("pause");
return 0;
}
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
