西安企业网站seo,中国建设银行官网招聘信息,北京公司注册代理,百度网站排名突然消失题目
请写一个整数计算器#xff0c;支持加减乘三种运算和括号。 示例1 输入#xff1a;“12” 返回值#xff1a;3示例2 输入#xff1a;“(2*(3-4))*5” 返回值#xff1a;-10示例3 输入#xff1a;“32*3*4-1” 返回值#xff1a;26
思路
经典的中缀表达式求值。…题目
请写一个整数计算器支持加减乘三种运算和括号。 示例1 输入“12” 返回值3示例2 输入“(2*(3-4))*5” 返回值-10示例3 输入“32*3*4-1” 返回值26
思路
经典的中缀表达式求值。常用思路将其转为后缀表达式后缀表达式的特点遇到运算符则将前两个数拿出来运算便于计算机计算边转边求值。读到左括号 ( 较为特殊读到左括号时直接入栈本题中运算符优先级左括号或栈顶为空、乘、加减 、右括号。读到右括号时一直出栈直到一个左括号出栈。
算法步骤
遍历字符串当 遍历到的字符是数字 时直接将其压入数字栈。否则当 遍历到的字符是运算符 时判断字符直到字符串读完 若符号栈为空则直接将其压入符号栈。若符号栈非空则判断符号栈栈顶的运算符优先级 若 遍历到的运算符符号的优先级 符号栈栈顶元素的优先级或符号栈空则将读取的运算符压入符号栈。若 遍历到的运算符符号的优先级 ≤ 符号栈栈顶元素的优先级则将其出栈并从数字栈弹出两个元素进行该运算先弹出的为右操作数后弹出的为左操作数将结果压入数字栈。 最后若符号栈非空则弹出栈顶元素并从数字栈弹出两个元素来进行该运算重复该操作直到符号栈空。符号栈为空后弹出数字栈栈顶元素作为结果。返回数值站栈顶元素作为最终结果。
int solve(string s) {stackchar sign;stackint num;for (int i 0; i s.length(); i) {//若当前遍历到的字符为数字则将连续的数放入val栈if (s[i] 0 s[i] 9) {int rear i;while ((rear 1) s.length() s[rear 1] 0 s[rear 1] 9) {rear;}int n 0;for (int j rear; j i; j--) {n (s[j] - 0) * pow(10, (rear - j));}i rear;num.push(n);}//【优先级较大】当前遍历到的字符为(、* 或 ops符号栈为空则将该符号压入符号栈else if (s[i] ( || s[i] *|| sign.size() 0 ){sign.push(s[i]);}//【优先级较小】当前遍历到的字符为、-else if (s[i] || s[i] -) {while (1) {if (sign.size() 0)break;if (sign.top() *) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 * n2);}else if (sign.top() ) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 n2);}else if (sign.top() -) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 - n2);}else {break;}}sign.push(s[i]);}// 读到右括号时符号栈就一直出栈直到一个左括号出栈。else if (s[i] )) {while (1) {if (sign.size() 0) {break;}else if (sign.top() () {sign.pop();break;}else if (sign.top() ) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 n2);}else if (sign.top() -) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 - n2);}else if (sign.top() *) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 * n2);}}}}//最后若符号栈非空则弹出栈顶元素并从数字栈弹出两个元素来进行该运算。重复该操作直到符号栈空。while (sign.size() ! 0) {if (sign.top() ) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 n2);}else if (sign.top() -) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 - n2);}else if (sign.top() *) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 * n2);}}//弹出数字栈栈顶元素即得结果。return num.top();
}实例
#include iostream
#include stack
using namespace std;int solve(string s) {// write code herestackchar sign;stackint num;for (int i 0; i s.length(); i) {//若当前遍历到的字符为数字则将连续的数放入val栈if (s[i] 0 s[i] 9) {int rear i;while ((rear 1) s.length() s[rear 1] 0 s[rear 1] 9) {rear;}int n 0;for (int j rear; j i; j--) {n (s[j] - 0) * pow(10, (rear - j));}i rear;num.push(n);}//若 当前遍历到的字符为(、* 或 ops符号栈为空则将该符号压入符号栈else if (s[i] ( || s[i] *|| sign.size() 0 ){sign.push(s[i]);}//若 当前遍历到的字符为、-else if (s[i] || s[i] -) {while (1) {if (sign.size() 0)break;if (sign.top() *) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 * n2);}else if (sign.top() ) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 n2);}else if (sign.top() -) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 - n2);}else {break;}}sign.push(s[i]);}else if (s[i] )) {while (1) {if (sign.size() 0) {break;}else if (sign.top() () {sign.pop();break;}else if (sign.top() ) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 n2);}else if (sign.top() -) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 - n2);}else if (sign.top() *) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 * n2);}}}}//最后若符号栈非空则弹出栈顶元素并从数字栈弹出两个元素来进行该运算。重复该操作直到符号栈空。while (sign.size() ! 0) {if (sign.top() ) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 n2);}else if (sign.top() -) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 - n2);}else if (sign.top() *) {sign.pop();int n2 num.top();num.pop();int n1 num.top();num.pop();num.push(n1 * n2);}}//弹出数字栈栈顶元素即得结果。return num.top();
}int main()
{string mys 13*(52);cout mys solve(mys) endl;return 0;
}
