算法训练表达式计算

2019-11-08 01:29:52

字体：大中小

来源：转载

供稿：网友

这里写图片描述

上网查了一下，采用后缀表达式从中序表达式转换为后序表达式由于后续表达式更易计算机去解决，所以我们在运算算术表达式时要先转换为后序的。方法如下建立符号栈顺序扫描中序表达式 a）是数字，直接输出 b）是运算符 i : “(” 直接入栈 ii : “)” 将符号栈中的元素依次出栈并输出, 直到 “(“, “(“只出栈, 不输出 iii: 其他符号, 将符号栈中的元素依次出栈并输出, 直到遇到比当前符号优先级更低的符号或者”(“。将当前符号入栈。扫描完后, 将栈中剩余符号依次输出例 : 3+(2-5)*6/3遇到 3 是数字输出表达式 : 3 符号栈 :遇到”+” 号 , 利用法则iii ，栈中没有优先级更低的符号，直接入栈表达式 : 3 符号栈 : +遇到”(” , 利用法则i, 直接入栈表达式 : 3 符号栈 : + (遇到”2” 输出表达式 : 3 2 符号栈 : + (遇到 “-” , 利用法则iii , 遇到”(“, 没有出栈符号, 直接入栈表达式 : 3 2 符号栈 : + ( -遇到”5” 输出表达式 : 3 2 5 符号栈 : + ( -遇到”)” 利用法则ii , 将”-“号出栈输出, “(” 出栈表达式 : 3 2 5 - 符号栈 : +遇到”*” 利用法则ii , “*” 比”+”的优先级低, 所以遇到优先级更低的符号, 不用出栈, 将”*”入栈表达式 : 3 2 5 - 符号栈 : + *遇到”6” 输出表达式 : 3 2 5 - 6 符号栈 : + *遇到”/” 利用法则ii , “/” 与”*”的优先相同, 就是说”*”不是优先级更低的符号, 所以出栈输出, 继续 “+”比”/”的优先级低, 不用出栈, 将”/”入栈表达式 : 3 2 5 - 6 * 符号栈 : + /遇到”3” 输出表达式 : 3 2 5 - 6 * 3 符号栈 : + /扫描完成将符号栈内的符号依次输出表达式 : 3 2 5 - 6 * 3 / +直接过的代码# include <iostream># include <string.h>#include <string>#include<stack> #include<windows.h> using namespace std;stack<string> s_ch;//符号栈 stack<string> s_num; //数值栈 stack<string> s_temp;int strtoint(string s){ return atoi(s.c_str());}string inttostr(int num){ char a[10]; itoa(num,a,10); string b; b = a; return b;}int main(){ int a,b; string s; string f=""; string s1 = ""; string temp = ""; cin >> s; int len; len = s.length(); for (int i = 0; i<len; i++) { s1 = s[i]; if (s[i] <= '9' && s[i] >= '0') { temp += s[i]; if (s[i + 1] > '9' || s[i + 1] < '0') { s_num.push(temp); temp = ""; } } else { if (s[i] == '(') s_ch.push("("); else if (s[i] == ')') { while (s_ch.top() != "(") { s_num.push(s_ch.top()); s_ch.pop(); } s_ch.pop(); } else { if(s_ch.empty()) s_ch.push(s1); else { if ((s[i] == '+' || s[i] == '-') && (s_ch.top() == "+" || s_ch.top() == "-" || s_ch.top() == "*" || s_ch.top() == "/")) { s_num.push(s_ch.top()); s_ch.pop(); s_ch.push(s1); } else if ((s[i] == '+' || s[i] == '-') && (s_ch.top() == "(")) s_ch.push(s1); if ((s[i] == '*' || s[i] == '/') && (s_ch.top() == "+" || s_ch.top() == "-" || s_ch.top() == "(")) s_ch.push(s1); else if ((s[i] == '*' || s[i] == '/') && (s_ch.top() == "*" || s_ch.top() == "/")) { s_num.push(s_ch.top()); s_ch.pop(); s_ch.push(s1); } } } } } while (!s_ch.empty()) { s_num.push(s_ch.top()); s_ch.pop(); } while(!s_num.empty()) { s_temp.push(s_num.top()); s_num.pop(); } int flag = 0; string s3; while (!s_temp.empty()) { s3 = s_temp.top(); f += s3; if(s3 != "+" && s3 != "-" && s3 != "*" && s3 != "/") { s_num.push(s3); } else { flag = 1; b = strtoint(s_num.top()); s_num.pop(); a = strtoint(s_num.top()); s_num.pop(); if(s3 == "+") a += b; if(s3 == "-") a -= b; if(s3 == "*") a *= b; if(s3 == "/") a /= b; s_num.push(inttostr(a)); } s_temp.pop(); } if(flag) cout << a; else cout <<strtoint(s3); //cout << ' ' << f;}

上一篇：HTTP(Hyper Text Transfer Protocol 超文本传输协议)学习笔记

下一篇：ABAP里面游标的使用