编译原理笔记（1）

因为参加了CCF的认证考试，加之这假期事情比较少，所以决定静下心来学习几个算法，按照CSP网站上的题目去做，第二道题便是多项式求和。以前在数据结构课上，便了解过多项式求和利用的是栈这个数据结构。不过一直以来遇到需要自己实现的数据结构，我便有点犯怵。不过这次既然决定学习了，所以便决定解决这个问题。

要求如下：

1. ‘+’、‘-’、‘x’、‘/’ 分别表示加减乘除四个基本操作
2. ‘（’、‘）’分别表示左右括号
3. 要求计算最后结果

思路

1. 分别需要两个栈来分别存放，操作数和操作码。
2. 将多项式作为字符串进行输入。
3. 之后遍历字符串，遇到操作数直接进栈，遇到操作码则较为复杂。
4. 遇到操作码,需要和栈顶存放的操作码进行比较，若高于栈顶操作码，说明之后的出栈的顺序不会影响操作码的计算结果，操作码直接进栈即可。（因为出栈时是后入栈的先出栈，也先计算）
5. 若低于栈顶操作码，则需要将栈顶操作码出栈，操作数出栈两次将结果进行计算，之后再将结果入栈。
6. 若遍历结束，也即遇到’\0’符号，若这是操作码栈中不为空，则需依次出栈计算结果。直到操作码栈为空。

C/C++代码：

#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <list>

using namespace std;
const int optContainer[8][8]={{-1,0,-1,-1,2,-1,2,-1},{2,1,1,1,2,1,2,1},{-1,1,1,1,2,1,2,1},{-1,1,-1,1,2,1,2,-1},{2,2,2,2,2,2,2,2},{-1,1,-1,1,2,1,2,-1},{2,2,2,2,2,2,2,2},{-1,1,1,1,2,1,1,1}};
int isopn(char i);
int optCompare(char opt1,char opt2);
int opt_cal(char i,int a,int b);
int main() {
    stack<char> optStack;
    stack<int> opnStack;

    string expression;
    cin>>expression;
	int panduan = 0;
    for(unsigned int i=0;i<=expression.length();++i){
        if(isopn(expression[i])) {
			
			if (panduan == 1) {
				int temp_num = opnStack.top();
				opnStack.pop();
				opnStack.push(temp_num*10+expression[i] - '0');
			}
			else opnStack.push(expression[i]-'0');
			panduan = 1;
        }
        else {
			panduan = 0;
            if(optStack.empty()){
				if (opnStack.empty()) exit(0);
                optStack.push(expression[i]);
            }
            else
                switch (optCompare(optStack.top(),expression[i])) {
                    case 1: {
                        char opt = optStack.top();
                        optStack.pop();
                        optStack.push(expression[i]);
                        int opn_a = opnStack.top();
                        opnStack.pop();
                        int opn_b = opnStack.top();
                        opnStack.pop();
                        opnStack.push(opt_cal(opt, opn_a, opn_b));
                        break;
                    }
                    case 0: {
                        optStack.pop();
                        break;
                    }
                    case -1: {
                        optStack.push(expression[i]);
                        break;
                    }
					case 3: {
						while (optStack.size() != 0) {
							char opt = optStack.top();
							optStack.pop();
							int opn_a = opnStack.top();
							opnStack.pop();
							int opn_b = opnStack.top();
							opnStack.pop();
							opnStack.push(opt_cal(opt, opn_a, opn_b));
							
						}
					}

                }


        }
    }
	cout << opnStack.top();
    system("pause");
    return 0;
}
int isopn(char i){
    if (i<=57 &&i>=48){
        return 1;
    }
    else return 0;
}

int opt_cal(char i,int a,int b){
    switch (i){
        case '*':return a * b;
        case '/':return b/a;
        case '+':return a+b;
        case '-':return b-a;
        default:return 0;
    }
}


int optCompare(char top_opt,char new_opt){
	if (new_opt == '\0') return 3;

    return optContainer[top_opt-'('][new_opt-'('];

}

Python代码：

def com(op1,op2):
    p1=["x","/"]
    p2=["+","-"]
    if (op1 in p1) and (op2 in p2):
        return True
    else:
        return False
def operate(operation,p1,p2):
    if operation=="x":
        return p1*p2
    elif operation=="/":
        return p2//p1
    elif operation=="+":
        return p1+p2
    else :
        return p2-p1


num=int(input())
opt={"+":{"+":1,"-":1,"x":0,"/":0},"-":{"+":1,"-":1,"x":0,"/":0},"x":{"+":1,"-":1,"x":1,"/":1},"/":{"+":1,"-":1,"x":1,"/":1}}
expression=[]

for i in range(num):
    expression.append(input())
for i in expression:
    letter=[]
    operation=[]
    c=list(i)
    panduan=0;
    for j in range(len(c)):
        if c[j].isdigit():
            if panduan==1:
                num_temp=letter.pop()
                letter.append(int(num_temp*10+int(c[j])))
            else:
                letter.append(int(c[j]))
            panduan=1
        else:
            if len(operation)==0:
                operation.append(c[j])
            elif (opt[operation[len(operation)-1]])[c[j]]==1:
                a=letter.pop()
                b=letter.pop()
                op=operation.pop()
                letter.append(operate(op,a,b))
                operation.append(c[j])
            else:
                operation.append(c[j])
            panduan=0
    while(len(operation)!=0):
        a=letter.pop()
        b=letter.pop()
        op=operation.pop()
        letter.append(operate(op,a,b))
    if int(letter[0])==24:
        print("Yes")
    else:
        print("No")