栈的应用-表达式求值
表达式的三种表示方法 设 Exp = S1 OP S2
OP S1 S2 为前缀表示法S1 OP S2 为中缀表示法S1 S2 OP 为后缀表示法前缀式的运算规则为:
连续出现的两个操作数和在它们之前且紧靠它们的一个运算符构成一个最小表达式;
后缀式的运算规则为:
连续出现的两个操作数和在它们之后且紧靠它们的一个运算符构成一个最小表达式;
利用栈从后缀式求值原理：遇到运算数则入栈，遇到操作符则出栈2个数，计算，结果入栈1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221 ...
稀疏矩阵的压缩存储
12345678910111213#include <iostream>using namespace std;struct Triple{ //三元组 int row, col; //非零元素行号/列号 int value; //非零元素的值 void operator=(Triple &R) //赋值 { row = R.row; col = R.col; value = R.value; }};
12345678910111213141516171819202122class SparseMatrix{private: int Rows, Cols, Terms; //行／列／非零元素数 Triple *smArray; //三元组表public: SparseMatrix(int Rw, int Cl ...
栈的应用-中缀表达式求值
原理：使用两个栈操作符栈OPTR (operator)，操作数栈OPND(operand)，为了实现这种计算，需要考虑各操作符的优先级
代码思路：
建立并初始化OPTR栈和OPND栈，然后在OPTR栈中压入一个“#”
扫描中缀表达式，取一字符送入ch。
当ch != ‘#’ 或OPTR栈的栈顶 != ‘#’时, 执行以下工作, 否则结束算法。在OPND栈的栈顶得到运算结果。
循环过程：
若ch是操作数，进OPND栈，读下一字符到ch；
若ch是操作符，比较icp(ch)的优先级和isp(OPTR)的优先级：
若icp(ch) > isp(OPTR)，则ch进OPTR栈，读下一字符到ch；
若icp(ch) < isp(OPTR)，则从OPND栈退出a2和a1，从OPTR栈退出θ, 形成运算指令 (a1)θ(a2)，结果进OPND栈,不读入下一字符而是继续比较栈顶元素；
若icp(ch) == isp(OPTR) 且ch == ‘)’，则从OPTR栈退出’(‘，对消括号，然后从中缀表达式取下一字符送入ch；
代码实现：
1234567891011121314151 ...
