855学习记录数据结构杂谈(1)——炎泽汐$de$ Blog

文章目录[隐藏]

• 表达式计算
• 压缩存储

后缀表达式计算

---

int op(int a, int b, char Op){
	if(Op == '+'){
		return a + b;
	}
	
	if(Op == '-'){
		return a - b;
	}
	
	if(Op == '*'){
		return a + b;
	}
	
	if(Op == '/'){
		if(b == 0){
			return 0;
		}
		return a / b;
	}
}

int com(vector<char>& exp){
	int a, b, ans;
	char Op;
	stack<int> st;
	
	for(int i = 0; i < exp.size(); i++){
		if(exp[i] >= '0' && exp[i] <= '9'){
			st.push(int(exp[i] - '0'));
		}else{
			Op = exp[i];
			b = st.pop();
			a = st.pop();
			ans = op(a, b, Op);
			st.push(ans);
		}
	}
	return ans;
}

中缀转后缀

---

      $isp$叫做栈内($in$ $stack$ $priority$)优先数$icp$叫做栈外($in$ $coming$ $priority$)优先数。操作符优先数相等的情况只出现在括号配对或栈底的’#’号与输入流最后的’#’号配对时。前者将连续退出位于栈顶的操作符,直到遇到'(‘为止。然后将'(‘退栈以对消括号，后者将结束算法。

      算法流程如下：

$Step1:$初始化符号栈，将结束符’#’入栈；

$Step2:$读入字符$ch$；

$Step3:$若$ch==$’#’且栈顶元素亦为’#’则结束算法。

$Step4:$若$ch$为数字则直接输出，并返回$Step2$，否则进入$Step5$；

$Step5:$判断栈顶操作符$op$和$ch$的优先级：若$icp(ch) > isp(op)$，令$ch$入栈并返回$Step2$；若$icp(ch) < isp(op)$退栈、输出并返回$Step5$；若$icp(ch) == isp(op)$则直接退栈，若退出的是'('则返回$Step2$，否则继续比较优先级；

unordered_map<char, int> isp;
unordered_map<char, int> icp;

void init(){
    isp['#'] = 0;
    icp['#'] = 0;
    isp['('] = 1;
    icp['('] = 6;
    isp[')'] = 6;
    icp[')'] = 1;
    isp['+'] = 3;
    icp['+'] = 2;
    isp['-'] = 3;
    icp['-'] = 2;
    isp['*'] = 5;
    icp['*'] = 4;
    isp['/'] = 5;
    icp['/'] = 4;
    isp['%'] = 5;
    icp['%'] = 4;
}

void zhong2hou(vector<char>& exp){
    stack<char> st;
    char op, ch;
    int i = 0;
    ch = exp[i++];
    st.push(ch);
    ch = exp[i++];
    init();
		
    while(!st.empty() && ch != '#'){
        if(exp[i] >= '0' && exp[i] <= '9'){
            cout << int(exp[i] – '0');
            ch = exp[i++];
        }else{
            op = st.top();
            if(isp[op] < icp[ch]){
                st.push(ch);
                ch = exp[i++];
            }else if(isp[op] > icp[ch]){
                st.pop();
                cout << op;
            }else{
                st.pop();
                if(op == '('){
                    ch = exp[i++];
                }
            }
        }
    }
}

对称矩阵

---

      对称矩阵可压缩存储为上/下三角矩阵以节省空间，通常使用一维数组来按行储存，位置对应关系如下（数组从 0 计数，矩阵从 1 计数）：

下三角情形：

$$
LOC\left( i,j \right) \begin{cases}
\frac{i\cdot \left( i-1 \right)}{2}+j-1& i\ge j\\
LOC\left( j,i \right)& i< j\\ \end{cases} $$ 上三角情形： $$ LOC\left( i,j \right) \begin{cases} \frac{\left( 2n-i+1 \right) \cdot \left( i-1 \right)}{2}+j-i& i\le j\\ LOC\left( j,i \right)& i< j\\ \end{cases} $$

稀疏矩阵

---