其实是老师布置的作业。稍微写了些注释，然后直接把代码扔上来，希望能帮到有需要的同学。

拒绝抄作业，写那么多注释就是让你来读懂代码的。

栈-使用C++类实现

// 使用C++类 实现栈的数据结构
template <typename T>
class Stack
{
private:
    T *dat;             // 用于访问存储空间的指针
    int ptr;            // 存储栈顶元素下标的变量，相当于指向栈顶的指针
    const int MAX_SIZE; // 栈的最大容量
public:
    Stack(int size) : MAX_SIZE(size)
    {
        // 构造函数 在实例化对象时决定栈的大小并申请内存
        // ptr初值为-1，表示栈为空
        dat = new T[MAX_SIZE];
        ptr = -1;
    }
    bool empty() // 栈是否为空
    {
        return ptr == -1 ? 1 : 0;
    }
    int count() // 栈中元素计数
    {
        return ptr+1;
    }
    int push(T now) // now元素入栈
    {
        if (ptr + 1 == MAX_SIZE)
            return -1;
        dat[++ptr] = now;
        return 0;
    }
    int pop() // 删除栈顶元素
    {
        if (ptr == -1)
            return -1;
        ptr--;
        return 0;
    }
    T top() // 返回栈顶元素
    {
        return dat[ptr];
    }
    ~Stack()
    {
        delete[] dat;
    }
};

以下题目中对于类的声明部分均省略。

进制转换问题

【问题描述】根据课堂讲授，请用“顺序栈”解决进制转换问题，不采用顺序栈，不给分。
【输入形式】十进制数据和待转换的进制
【输出形式】转换后的数据
【样例输入1】1348 8
【样例输出1】2504
【样例输入2】2608 16
【样例输出2】A30

// 使用顺序栈解决进制转换问题
void convert(Stack<int> &s, int dat, int t) // 进制转换 t表示t进制
{
    while (dat) // 当dat非0重复操作
    {
        s.push(dat % t); //把余数放入栈中
        dat /= t;
    }
    return;
}
char dict[] = "0123456789ABCDEF"; // 字典，把栈中存储的元素转换为对应的字符（主要用于16进制）
int main()
{
    int dat, t;
    // 定义一个长度为32的栈
    Stack<int> res(32); 
    
    scanf("%d%d", &dat, &t);
    convert(res, dat, t);
    //输出栈中元素
    while (!res.empty())
    {
        printf("%c", dict[res.top()]);
        res.pop();
    }
    putchar('\n');
    return 0;
}

字符串镜像

【问题描述】试写一个算法，识别依次读入的一个以“@”为结束符的字符序列是否为形如 “序列1&序列2” 模式的字符序列。其中序列1和序列2都不含字符 “&”，且序列2是序列1的逆序列。例如，“ a+b&b+a ”是属该模式的字符序列，而 “1+3&3-1”则不是。

【输入形式】 以@为结尾的一串字符

【输出形式】若符合模式则输出字符串长度，否则输出no

【样例输入】a+b&b+a@

【样例输出】3

int main()
{
    Stack<char> s(1024); // 亲测有长度为2000的字符串数据。开一半就够了
    int cnt=0,flag=1; //cnt计数，flag标识是否为镜像串
    char now;
    // 前半部分 边读入边入栈
    do
    {
        now=getchar();
        s.push(now);
    } while (now!='&');

    s.pop(); // 把栈顶的'&'删掉
    cnt=s.count();
    // 后半部分 边读入边比较
    do
    {
        now=getchar();
        if(now!=s.top() && now!='@')
            flag=0;
        s.pop();
    } while (now!='@');

    if(flag)
        printf("%d\n",cnt);
    else
        printf("no\n");
    
    return 0;
}

表达式求值

很重要的算法，一定要掌握！

【问题描述】栈的应用，给定一个以“#”作为结束符的算式，求出算式的结果

【输入形式】以“#”结尾的表达式，运算数为正整数。每个表达式占一行。

【输出形式】输出表达式运算的结果。

【样例输入1】4+2.53*3-10/5#

【样例输出1】9.59

【样例输入2】3*(7.91-2)#

【样例输出2】17.73

// 全部函数采用指针now来读取字符串，并且指针now为引用传参，便于标记读到哪一位了。
// 从当前位置开始，读入字符，将其转化为浮点数并存入到引用变量ans中。(指针now移到这个数后一位(应当是符号))
// 返回值表示是否有读到一个数字。0为没有读入。
inline bool readnum(char *&now,float &ans) 
{
    if(*now<'0' || *now>'9') return 0;
    do
    {
        ans *= 10;
        ans += *now-'0';
        now++;
    } while (*now >= '0' && *now <= '9'); // 转换整数部分
    if (*now == '.')                      // 如果有小数部分，则转换
    {
        now++; //跳过小数点
        float flag=0.1;
        do
        {
            ans += (*now-'0')*flag;
            flag *= 0.1;
            now++;
        } while (*now>='0'&&*now<='9'); // 转换小数部分
    }
    return 1;
}
// 运算优先级比较函数，只考虑了四则运算
inline bool cmp(char a,char b) 
{
    int a1 = (a=='*' || a=='/')?1:0;
    int b1 = (b=='*' || b=='/')?1:0;
    return a1<=b1;
}
// 运算函数，直接从栈中取出运算符与操作数
// 因为该函数调用前，算法可以保证栈里面有元素，没有判断栈是否为空。
// 同样通过引用传参的方式使函数内可以访问栈中元素
inline float calc(Stack<float> &ovs,Stack<char> &optr) 
{
    float b=ovs.top(); ovs.pop();
    float a=ovs.top(); ovs.pop();
    char opt=optr.top();optr.pop();
    switch (opt)
    {
    case '+':
        return a+b;
    case '-':
        return a-b;
    case '*':
        return a*b;
    case '/':
        return a/b;
    default:
        return -1;
    }
}
float deal(char* &now)
{
    // 分别为运算数栈与运算符栈
    Stack<float> ovs(64);
    Stack<char> optr(64);
    while(1)
    {
        if (*now == '(') // 若读到括号，则进入递归，单独处理括号中的内容。
        {
            now++;
            ovs.push(deal(now)); // 处理完后返回，压入运算数栈。
        }

        float num = 0; // 若接下来是一个数，就放进这个变量里，然后再进栈
        if (readnum(now, num))
            ovs.push(num);
        else // 否则说明读到了一个运算符，开始处理表达式
        {
            // 运算符栈不为空，这时候需要比较当前运算符和栈中运算符优先级
            // 栈里面运算符优先级高，就先把它算掉再管当前的运算符
            // 否则先搁置当前运算符，放入运算符栈里面，下一次遇到运算符的时候再管。（以防后面有优先级更高的运算符）
            while (!optr.empty())
            {
                if (cmp(*now, optr.top()))
                    ovs.push(calc(ovs, optr));
                else
                {
                    optr.push(*(now++)); // 这里入栈之后就now++了，表示这个符号处理完了
                    break;
                }
            }
            if (*now == '#' || *now == ')') // 读到这两个说明这一段表达式结束了，退出外层循环。
                break;
            // 如果当前还是个符号，只有可能是因为opt栈是空的，没进入while循环处理掉
            // 说明它是第一个进栈的运算符，先留着
            if ((*now < '0' || *now > '9'))
                optr.push(*(now++));
        }
    }
    // 最后ovs栈里面只可能剩下一个元素，就是运算结果。
    return ovs.top(); 
}
int main()
{
    char raw[128],*p=raw;
    cin.getline(raw,127);
    float ans=deal(p);
    printf("%.2f\n",ans);
    return 0;
}