guopengli 发布的文章

数据结构课设 环境: vs2013



#include<stack>
using namespace std;
//判断是否是运算符,是的话返回true否则返回false
bool tell(char ch)
{
    char ops[] = "+-*/";
    for (int i = 0; i < sizeof(ops) / sizeof(char); i++)
    {
        if (ch == ops[i])
            return true;
    }
    return false;
}
// 比较两个操作符的优先级
int Precedence(char op1, char op2)
{
    if (op1 == '(')
        return -1;
    if (op1 == '+' || op1 == '-')
    {
        if (op2 == '*' || op2 == '/')
            return -1;
        else
            return 0;
    }

    if (op1 == '*' || op1 == '/')
    {
        if (op2 == '+' || op2 == '-')
            return 1;
        else
            return 0;
    }
}

// 中缀表达式转换成后缀表达式
/*
1.遇到操作数:直接输出(添加到后缀表达式中)
2.栈为空时,遇到运算符,直接入栈
3.遇到左括号:将其入栈
4.遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出。
5.遇到其他运算符:加减乘除:弹出所有优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈
6.最终将栈中的元素依次出栈,输出。
*/
void change(char* inFix, char* postFix)
{
    int j = 0, len;
    char c;
    stack<char> st;

    len = strlen(inFix);

    for (int i = 0; i < len; i++)
    {
        c = inFix[i];

        if (c == '(')//遇到(,直接入栈
            st.push(c);
        else if (c == ')')//遇到)进行判断
        {
            while (st.top() != '(')
            {
                postFix[j++] = st.top();//栈顶不是左括号,出栈,进入后缀表达式
                st.pop();
            }
            st.pop();
        }
        else
        {
            if (!tell(c))//如果c不是运算符,直接入栈
                st.push(c);
            else//是运算符
            {
                while (st.empty() == false && Precedence(st.top(), c) >= 0)//遇到运算符,栈非空,弹出所有优先级大于或者等于该运算符的栈顶元素
                {
                    postFix[j++] = st.top();//先取值
                    st.pop();//再删除
                }
                st.push(c);//栈为空,遇到运算符则运算符直接入栈or上一步之后将该运算符入栈
            }
        }
    }

    while (st.empty() == false)//最后栈依旧不是空的,则全部出栈
    {
        postFix[j++] = st.top();
        st.pop();
    }
    postFix[j] = 0;
}
// 后缀表达式求值
double postFixEval(char* postFix,int* a,int* b)
{
    stack<char> st;
    int len = strlen(postFix);
    char c;

    for (int i = 0; i < len; i++)
    {
        c = postFix[i];
        if (tell(c) == false)//不是运算符
        {
            st.push(c - '0');
        }
        else
        {
            char op1, op2;
            int val=0,z=0;

            op1 = st.top();
            st.pop();
            op2 = st.top();
            st.pop();

            switch (c)
            {
            case '+':
                val = op1 + op2;
                break;
            case '-':
                val = op2 - op1;
                break;
            case '*':
                val = op1 * op2;
                break;
            case '/':
                if (op1 != 0)
                    val = op2 / op1;
                else
                {
                    int temp;
                    temp=*b;
                    *a = temp;
                    goto second;
                    
                }
                
            second: break;
                
            }
            st.push(val);
        }
    }

    return st.top();
}
//操作函数
int exe()
{
    char inFix[100];
    char postFix[100];
    double val;
    int z=0,z1=1;
    re:printf("请输入一个中缀表达式\n");
    while (1)
    {

        gets_s(inFix);
        if (strlen(inFix) == 0)
            continue;
        change(inFix, postFix);
        printf("后缀表达式为 %s ", postFix);
        printf("\n");
        val = postFixEval(postFix,&z,&z1);
        if (z == 0)
            printf("结果是%.0lf\n", val);
        else
        {
            printf("输入表达式不合法,除数不能为0,请重新输入,谢谢\n");
            goto re;
        }
        return 0;
    }



}

int main()
{
    char inFix[100];
    int a;
    while (1)
    {
        printf("------------操作菜单------------\n");
        printf("   1:执行操作      ");
        printf("2:退出程序\n");
        printf("--------------------------------\n");
        printf("  按数字键选择要执行的操作: \n");
        scanf_s("%d", &a);
        printf("\n");
        if (a == 2)
            break;
        switch (a)
        {
         case 1:exe();  break;

        default:
            printf("输入的数字不正确,请重新输入\n");
            break;
        }

    }


    return 0;
}

POJ 1003 Hangover


Hangover

Description
How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We're assuming that the cards must be perpendicular to the table.) With two cards you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general you can make n cards overhang by 1/2 + 1/3 + 1/4 + ... + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table by 1/(n + 1). This is illustrated in the figure below.


POJ 1046 Color Me Less


Color Me Less

Description
A color reduction is a mapping from a set of discrete colors to a smaller one. The solution to this problem requires that you perform just such a mapping in a standard twenty-four bit RGB color space. The input consists of a target set of sixteen RGB color values, and a collection of arbitrary RGB colors to be mapped to their closest color in the target set. For our purposes, an RGB color is defined as an ordered triple (R,G,B) where each value of the triple is an integer from 0 to 255. The distance between two colors is defined as the Euclidean distance between two three-dimensional points. That is, given two colors (R1,G1,B1) and (R2,G2,B2), their distance D is given by the equation


POJ 3505 Tower Parking


Tower Parking

Description

There is a new revolution in the parking lot business: the parking tower. The concept is simple: you drive your car into the elevator at the entrance of the tower, and the elevator and conveyor belts drag the car to an empty parking spot, where the car remains until you pick it up. When you return, the elevator and conveyor belts move your car back to the entrance and you’re done.


POJ 1001 Exponentiation 求高精度幂


Exponentiation

Description
Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems. This problem requires that you write a program to compute the exact value of Rn where R is a real number ( 0.0 < R < 99.999 ) and n is an integer such that 0 < n <= 25.