开发自己的编程语言（二）——表达式计算

家人们好呀OK呀上一节内容中我们也是成功地拆分了token接下来我们要完成最重要的一步之一好像每一步都很重要——根据这些token进行基本的表达式计算。一、四则运算还记得上一节我们给运算符定义了优先级吗优先级越高的运算符应该越先被计算。例如这个式子14*2-3。先计算4*28然后189最后9-36。拆分成token后我们可以用栈来实现先计算优先级更高的运算符。我们准备两个栈一个存放数据及标识符一个专门放运算符。stackstring op; //运算符 stackData data; //其它token然后我们按照顺序依次把token放入该放入的栈中但要遵循这两个原则1.如果即将放入的运算符还没压入栈中的优先级大于栈顶运算符的优先级那么直接压入此运算符但不进行计算因为后续压入栈的运算符的优先级可能更高计算会导致优先级更低的运算符先把数据进行了计算2.如果即将放入的运算符的优先级小于等于栈顶运算符的优先级那么就可以计算此时栈顶的运算符因为栈顶优先级更高可以被先计算弹出此时栈顶的运算符和要计算的数据并把计算后的数据压入数据栈中一直执行此步骤直到遇到1的情况。这样说是不是有点绕啊我们举个例子还是计算14*2-3因为刚开始符号栈为空所以直接压入14stacks41dataop然后遇到了乘号。乘号的优先级比加号更高所以直接压入stacks24*1dataop接着是减号。减号优先级比栈顶的乘号低所以此时可以进行4*2的计算stacks即将放入的运算符-81dataop先别急着压入减号可以发现减号的优先级等于栈顶的加号所以继续计算stacks即将放入的运算符-9dataop因为符号栈已空此时压入减号并进行最后一步计算stacks39-dataopstacks6dataop此时表达式运算完毕数据栈栈顶元素就是计算结果。是不是很神奇实在无法理解的话就慢慢消化吧或者在评论区提问。实现代码如下void calc(string c){ //对单个运算符进行计算 if (data.size() op_level[c].second) return; //判断数据栈的数据个数是否大于等于运算符的操作数个数防止栈空时仍弹出数据 int b stoi(data.top().inf); data.pop(); int a stoi(data.top().inf); data.pop(); int x 0; if (c *) x a * b; else if (c /) x a / b; else if (c ) x a b; else if (c -) x a - b; data.push({to_string(x), _INT}); //压入计算的结果 } void CPrun(){ //对一行代码的运行函数 for (int i 0; i tokens.size(); i){ if (tokens[i].type _OP){ //如果是运算符 while (op.size() op_level[op.top()].first op_level[tokens[i].inf].first) { //优先级小于等于栈顶运算符则进行计算 calc(op.top()); op.pop(); } op.push(tokens[i].inf); //压入该运算符 } else data.push(tokens[i]); //如果不是运算符压入数据栈 } while (op.size()) { calc(op.top()); op.pop(); } } //main函数中 //进行某些操作。。。 to_tokens(s); CPrun(); cout 表达式的值为 data.top().inf endl endl; //输出栈顶最终计算结果如果你这一步做对了运行起来大致是这样的二、括号计算表达式有个很重要的东西——小括号。运算时应该最先计算括号内的东西但你有没有发现明明括号的计算优先级最高为啥代码中要把它的优先级设为1因为括号其实起到的是一个分隔的作用越是优先级低的运算符分隔作用越明显这有点反常识但括号在表达式中的作用确实是分隔。当遇到前括号的时候我们直接压入运算符栈即可相当于把接下来的运算符和前括号下面的运算符完全分隔了。接下来进行正常的运算。遇到后括号时按照普通的运算符的规则就行如果栈顶运算符优先级大于等于后括号的优先级则一直运算。当栈顶运算符为前括号时则弹出前括号一对括号中的所有计算就结束了。例如计算4*(23)分别压入4、乘号、前括号和2stacks2(4*dataop此时栈顶为前括号与前面的乘号隔开了直接压入加号和3stacks32(4*dataop然后遇到后括号进行加法计算弹出加号后又遇到前括号弹出前括号stacks54*dataop最后计算乘法得出答案为20。要用代码实现的话首先我们需要略微修改一下token的拆分因为括号不像、-等符号可以组成一些新的符号比如、--它是完全独立的所以需要进行特殊判断void to_tokens(string code){ tokens.clear(); for (int i 0; i code.size(); i){ string atoken ; if (is_num(code[i])){ while (i code.size() is_num(code[i])){ atoken code[i]; i; } --i; tokens.push_back({atoken, _INT}); } else if (is_op(code[i])){ if (code[i] ! ( code[i] ! )){ //对括号进行特殊判断和处理 while (i code.size() is_op(code[i]) code[i] ! ( code[i] ! )){ atoken code[i]; i; } --i; } else { atoken code[i]; } tokens.push_back({atoken, _OP}); } else if (is_var(code[i])){ while (i code.size() (is_num(code[i]) || is_var(code[i]))){ atoken code[i]; i; } --i; if ((op_level.count(atoken) 0)) tokens.push_back({atoken, _OP}); else tokens.push_back({atoken, _VAR}); } } }再修改一下CPrun函数void CPrun(){ while (op.size()) op.pop(); while (data.size()) data.pop(); for (int i 0; i tokens.size(); i){ if (tokens[i].type _OP){ while (op.size() op_level[op.top()].first op_level[tokens[i].inf].first tokens[i].inf ! ( op.top() ! () { calc(op.top()); //不对括号进行计算 op.pop(); } if (tokens[i].inf )){ if (op.size() op.top() () op.pop(); //后括号遇到前括号时则前括号弹出 } else op.push(tokens[i].inf); //正常压入运算符 } else data.push(tokens[i]); } while (op.size()) { calc(op.top()); op.pop(); } }大功告成如果每一步都准确无误的话运行起来是这样的目前我们已经完成了最基本的表达式的计算了。接下来我们会接触到更多关于编程语言本质上的东西函数、变量等。不过先别急好好地消化一下或者看看自己能不能在此基础上进行优化。谢谢大家最终代码如下#include iostream #include stack #include map #include vector #include utility using namespace std; #define _INT 0 #define _VAR 1 #define _OP 2 mapstring, pairint, int op_level { {*, {12, 2}}, {/, {12, 2}}, {, {11, 2}}, {-, {11, 2}}, {(, {1, 0}}, {), {1, 0}} }; struct Data{ string inf; int type; }; vectorData tokens; stackstring op; stackData data; bool is_num(char ch){ return (0 ch ch 9); } bool is_op(char ch){ string s ; s ch; return (op_level.count(s) 0); } bool is_var(char ch){ return ((A ch ch Z) || (a ch ch z) || ch _); } void to_tokens(string code){ tokens.clear(); for (int i 0; i code.size(); i){ string atoken ; if (is_num(code[i])){ while (i code.size() is_num(code[i])){ atoken code[i]; i; } --i; tokens.push_back({atoken, _INT}); } else if (is_op(code[i])){ if (code[i] ! ( code[i] ! )){ while (i code.size() is_op(code[i]) code[i] ! ( code[i] ! )){ atoken code[i]; i; } --i; } else { atoken code[i]; } tokens.push_back({atoken, _OP}); } else if (is_var(code[i])){ while (i code.size() (is_num(code[i]) || is_var(code[i]))){ atoken code[i]; i; } --i; if ((op_level.count(atoken) 0)) tokens.push_back({atoken, _OP}); else tokens.push_back({atoken, _VAR}); } } } void calc(string c){ if (data.size() op_level[c].second) return; int b stoi(data.top().inf); data.pop(); int a stoi(data.top().inf); data.pop(); int x 0; if (c *) x a * b; else if (c /) x a / b; else if (c ) x a b; else if (c -) x a - b; data.push({to_string(x), _INT}); } void CPrun(){ while (op.size()) op.pop(); while (data.size()) data.pop(); for (int i 0; i tokens.size(); i){ if (tokens[i].type _OP){ while (op.size() op_level[op.top()].first op_level[tokens[i].inf].first tokens[i].inf ! ( op.top() ! () { calc(op.top()); op.pop(); } if (tokens[i].inf )){ if (op.size() op.top() () op.pop(); } else op.push(tokens[i].inf); } else data.push(tokens[i]); } while (op.size()) { calc(op.top()); op.pop(); } } int main(){ string s; while (1){ cout 请输入表达式; getline(cin, s); //进行某些操作。。。 to_tokens(s); CPrun(); cout 表达式的值为 data.top().inf endl endl; } return 0; }