算法~简单的计算器（验证数学表达式是否合法~“状态机思想”）
- 2021 年 8 月 5 日
- 笔记
- 算法~简单的计算器（验证数学表达式是否合法~“状态机思想”）
算法~简单的计算器（验证数学表达式是否合法~“状态机思想”）
（有限状态机思想~进行状态转化，每个状态下，再进行判断是否转化状态）
1，为什么存储结构选择~栈？
因为栈可以去除括号，处理优先级~
举例：14-（5-6）
2，计算思路：
（1）全局变量compute_flag 标志是否可以进行计算，初始comute_flag = 0; 遇到 “+”或者“-”时，compute_flag = 1;
遇到“(”,compute_flag = 0;
（2）字符串数处理为整型数：number = number * 10 + ch – ‘0’；
【ps举例：String s=”1234″; for(int i = 0; i < s.length(); i++){ number = number*10+s[i]-‘0’; }】~‘ascall 码 相减（- ‘0’）获取该值 ’。
(3)状态机过程：循环遍历所有字符串元素：判断第一个字符串元素是否为空，空~continue；非空，进入startState~
stateState：若是（“0”~“9”）~进入numberState 状态；若是“（” 进入operationState状态。
然后，“退格”【因为循环体内部最后一行代码是 i++，退格回到s[i] 本身，进入numState 状态/opState状态。】
（全局变量：state、startState、numberState、opState）
(4) numberState 状态:
如果遇到（“0”~“9”）{//处理转化为整型数：number = number*10+s[i]-‘0’; }，否则 {
1，先将数number 压入数字栈number_stack; [字符串元素 1 2 3 + 遇到 + ，才知道前三个元素构成一个数字]
2, 判断compute_state 是否为1，为1，则进行计算；
3，num=0；进入操作符状态operationState~【遇到 +】，退格 i–;}
(5) operationState状态:{
1,判断是“+” 或“-”，压入操作符栈operation_stack; 修改compute_flag = 1;
2，如果 遇到 “(“, 修改compute_flag = 0; 进入数字状态 numberState~
3，如果遇到（“0”~“9”），进入数字状态 numberState，退格i –; ~
4,如果 遇到 “)”, 直接进行计算
}
（6）最后一个数number的处理【为什么有最后一个数 ，因为 之前的字符串元素 1 2 3 + 遇到 + ，才知道前三个元素构成一个数字，将数压栈，
但是最后一个数是因为遍历结束，并非有 “+”的提示】：
如果number != 0,则 压入数字栈number_stack,然后进行计算；
如果number == 0 且 栈空了，结果就是 0；
3，代码：
❀ 计算方法：
/** * 计算 */ void compute(std::stack<int> &number stack, std:: stack<char> &operation_stack){ if(number_state.size() < 2){ return; } int num2 = number_state.top(); number_state.pop(); int num1 = number_state.top(); number_state.pop(); if(operation_stack.top() == '+'){ number_state.push(num1 + num2); }else if(operation_stack.top() == '-'){ number_state.push(num1 - num2); } operation_stack.pop(); }
❀ “状态机”过程的计算方法：
int calculate(std::String s){ static const int START_STATE = 0; static const int NUMBER_STATE = 1; statci const int OPERATION_STATE = 2; std::stack<int> number_stack; std::stack<char> operation_stack; int number = 0; //用于将字符串数处理为整型数 int STATE = START_STATE; int compute_flag = 0; //全局变量compute_flag 标志是否可以进行计算 for(int i = 0; i < s.length(); i++){ if(s[i] == '') continue; switch (STATE){ case START_STATE: if(s[i] >= '0' && s[i] <= '9'){ STATE = NUMBER_STATE; }else { STATE = OPERATION_STATE; } i--; //退格，因为循环体内部最后一行代码是 i++，退格回到s[i] 本身 break; case NUMBER_STATE: if(s[i] >= '0' && s[i] <= '9'){ number = number * 10 + s[i] - '0'; }else{ number_stack(number); if(compute_flag == 1){ compute(number_stack,operation_stack); } number = 0; STATE = OPERATION_STATE; i--; //退格 } break; case OPERATION_STATE: if(s[i] == '+' || s[i] == '-'){ operation_stack.push(s[i]); compute_flag = 1; }else if(s[i] == '('){ STATE = NUMBER_STATE; compute_flag = 0; }else if(s[i] >= '0' && s[i] <= '9'){ STATE = NUMBER_STATE; i--; }else if(s[i] == ')'){ compute(number_stack,operation_stack); } break; } } //最后遍历凑成的一个数 if(number != 0){ number_stack.push(number); compute(number_stack,operation_stack); }else if(number == 0 && number_stack.empty()){ return 0; } return number_stack.top(); }
