C++多项式相加 & 括号匹配

yfme · 2019-12-20

写在前面

换了个主题

今天抽了点空出来换了个主题，感觉还行吧就不单独写个文章了。

然后太久没写博客了，Hexo是怎么用的都快忘干净了。

正文

情况就随便提两句完事，尽快进入正题吧。

这次的题目来源于C++的大作业，正好我在网上没有找到合适的代码，就自己写了一个，也将其分享出来。

这里主要弄的是数据结构，可能里面会有一些小问题，由于是一个很正常的作业，就没有细究了。

多项式相加

多项式相加我只写了链表的，没写顺序表的。

设有多项式A (x)和B (x)，
求C (x)= A (x)+B (x)

运算规则：将两个多项式中指数相同的项对应系数相加，若和不为零，则构成C (x)中的一项； A (x)和B (x)中所有指数不相同的项均复抄到C (x)中。

#include"iostream"
#include"stdlib.h"
using namespace std;

typedef int ElemType;

typedef struct node {
    ElemType a;//系数
    ElemType b;//指数
    struct node *next;
}NodeType;

class LinkList {
public:
    NodeType *Head;
    LinkList();
    ~LinkList();
    void Creat();
    void Print();
    int GetLength();
    int Locate(ElemType x);
    NodeType * GetElem(int i);
    void Insert(int i, ElemType a, ElemType b);
    void Delete(int i);
};

LinkList::LinkList() {
    Head = new NodeType;
    Head->next = 0;
}

int LinkList::GetLength() {
    int num = 0;
    NodeType *p;
    p = Head->next;
    while (p != NULL) {
        num++;
        p = p->next;
    }
    return(num);
}

void LinkList::Print() {
    NodeType *p;
    p = Head->next;
    cout << "D=";
    while (p != NULL) {
        cout << p->a << "X^" << p->b;
        if (p->next != NULL) {
            cout << " + ";
        }
        p = p->next;
    }
}

NodeType * LinkList::GetElem(int i) {
    NodeType *p = Head->next;
    int pos = 1;
    if (i<1 || i>GetLength()) {
        cout << "error" << endl;
        return 0;
    }
    while (pos < i) {
        p = p->next;
        pos++;
    }
    return p;
}

int LinkList::Locate(ElemType x) {
    NodeType *p;
    int loc = 1;
    p = Head->next;
    while (p != NULL && p->b != x) {
        p = p->next;
        loc++;
    }
    if (p != NULL) {
        return loc;
    }
    else {
        return -1;
    }
}

void LinkList::Insert(int i, ElemType a, ElemType b) {
    NodeType *p, *s;
    if (i<1 || i>GetLength() + 1) {
        return;
    }
    if (i == 1) {
        p = Head;
    }
    else {
        p = GetElem(i - 1);
    }
    s = new NodeType;
    s->a = a;
    s->b = b;
    s->next = p->next;
    p->next = s;
}

void LinkList::Delete(int i) {
    NodeType *p, *t;
    if (i<1 || i>GetLength()) {
        cout << "error" << endl;
        return;
    }
    if (i == 1) {
        p = Head;
    }
    else {
        p = GetElem(i - 1);
    }
    t = p->next;
    p->next = t->next;
    delete t;
}

void LinkList::Creat() {
    int i = 1;
    NodeType *p, *s;

    p = Head;
    cout << "请输入系数与指数（空格隔开）" << endl;
    while (1) {
        s = new NodeType;
        cout << "第" << i << "个：";
        cin >> s->a;
        if (s->a == -1) {
            break;
        }
        cin >> s->b;
        s->next = NULL;
        p->next = s;
        p = s;
        i++;
    }
}

LinkList:: ~LinkList()
{
    NodeType *p, *q;
    if (Head->next != 0)
    {
        q = Head->next;
        while (q != NULL)
        {
            p = q;
            q = q->next;
            delete p;
        }
    }
    delete Head;
}

void main()
{
    LinkList f;
    LinkList s;
    LinkList r;

    NodeType *p;

    cout << "请输入第一个多项式：" << endl;
    r.Creat();
    cout << endl;

    cout << "第一个多项式：";
    r.Print();
    cout << endl;

    cout << "请输入第二个多项式：";
    s.Creat();
    cout << endl;

    cout << "第二个多项式：";
    s.Print();
    cout << endl;

    p = f.Head->next;

    while (p != NULL) {
        int b = p->b;
        int a = p->a;
        int po = s.Locate(b);
        if (po != -1) {
            a += s.GetElem(po)->a;
            s.Delete(po);
        }
        r.Insert(r.GetLength() + 1, a, b);
        p = p->next;
    }

    p = s.Head->next;
    while (p != NULL) {
        int b = p->b;
        int a = p->a;
        r.Insert(r.GetLength() + 1, a, b);
        p = p->next;
    }
    cout << endl;
    cout << "相加结果：";
    cout << endl;
    r.Print();

    system("pause");
}

括号匹配

算术表达式中，可以包含圆括号()、方括号[] 。括号使用规则：出现左括号，必有相应的右括号与之匹配，每对括号之间可以嵌套，但不能出现交叉情况。

设计算法，检验算术表达式中括号的合法性。

方法：使用一个栈保存每个出现的左括号，扫描到右括号时，从栈中弹出左括号，检验匹配情况。遇到以下情况之一，说明括号不匹配：

扫描到一个右括号时栈已空，说明目前右括号多于左括号

栈中弹出的左括号与当前扫描到的右括号类型不同，说明括号交叉

算术表达式扫描完毕，栈中还有没有匹配的左括号，说明左括号多于右括号

顺序栈的数据结构（类及其成员函数的设计）

typedef char ElemType;
const int MAXSIZE = 100;

class SqStack {
private:
    ElemType elem[MAXSIZE];
    int top;
public:
    SqStack() {
        top = 0;
    }
    ~SqStack() {};
    int IsEmpty();
    void Push(ElemType e);
    ElemType Pop();
    //void Print();
    ElemType GetPop() {
        return elem[top];
    }
};


void SqStack::Push(ElemType e) {
    if (top == MAXSIZE - 1) {
        cout << "栈上溢错误" << endl;
        return;
    }
    top++;
    elem[top] = e;
}

ElemType SqStack::Pop() {
    ElemType x;
    x = elem[top];
    top--;

    return x;
}

int SqStack::IsEmpty() {
    if (top == 0) {
        return 1;
    }
    else {
        return 0;
    }
}

链栈的数据结构（类及其成员函数的设计）

typedef char ElemType;
typedef struct node {
	ElemType	data;
	struct node	*next;
}NodeType;

class LinkStack
{
public:
	NodeType *top;
	LinkStack()
	{
		top = NULL;
	}

	~LinkStack()
	{
		while (!IsEmpty())
			Pop();
	}

	int IsEmpty()
	{
		if (top == NULL)
			return(1);
		else return(0);
	}

	void Push(ElemType e)
	{
		NodeType *p;
		p = new NodeType;  p->data = e;  p->next = top;  top = p;
	}

	ElemType Pop()
	{
		NodeType *p;   ElemType x;
		x = top->data;  p = top;  top = top->next; delete p;
		return(x);
	}

	ElemType GetTop()
	{
		return(top->data);
	}
};

括号匹配函数的设计

int Matching()
{
	LinkStack s;

	cout << "请输入符号（回车键结束）：";
	char ch = getchar();
	while (ch != '\n')
	{
		if (ch == '(')
		{
			s.Push(ch);
		}
		else if (ch == '[')
		{
			s.Push(ch);
		}
		else if (ch == '{')
		{
			s.Push(ch);
		}
		else if (ch == ')')
		{
			if (!s.IsEmpty())
			{
				if (s.Pop() != '(')
				{
					return 0;
				}
			}
		}
		else if (ch == ']')
		{
			if (!s.IsEmpty())
			{
				if (s.Pop() != '[')
				{
					return 0;
				}
			}
		}
		else if (ch == '}')
		{
			if (!s.IsEmpty())
			{
				if (s.Pop() != '{')
				{
					return 0;
				}
			}
		}
		ch = getchar();
	}

	if (s.IsEmpty())
	{
		return(1);
	}
	else {
		return(0);
	}
}

程序主函数的设计

void main()
{
	int n = Matching();
	if (n)
	{
		cout << "匹配成功！";
	}
	else {
		cout << "匹配失败！";
	}

	system("pause");
}

最后

这里就不赘述顺序存储和链式存储的区别和对比了，我也不是主要学C++的，学校开设的大学计算机基础课程就要求学这玩意，希望有和我同样需求的人能够通过这篇用到和课本知识匹配的恰到好处的文章来简化作业。

极乌客