首页 > 代码库 > 表达式求值
表达式求值
思路:参考严蔚敏的数据结构书籍
两个栈:操作数栈OPND,操作符号栈OPTR
在表达式后加=
符号栈初始化时=入栈
每读一个字符:
当它是#并且符号栈栈顶也是#时结束算法
当它是操作数时,进数栈
当它是符号时:
1.如果符号栈顶的优先级小于它,进符号栈
2.如果符号栈顶的优先级大于它,出两个数,出一个符号,计算后入数栈
3.如果与符号栈顶优先级相等,那说明是栈顶为(,它是),(出栈
首先对书上代码进行改进,严书的代码只能计算结果和输入在10以内的数字,我们要对111等一个字符以上的数字进行处理
#include <iostream> #include <cstdio> #include <cmath> #include <assert.h> #include <map> #include <stack> using namespace std; map<char,int> mp; char Precdede[][7] = { {'>','>','<','<','<','>','>'},//请参照严书上面的优先关系 {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=',0}, {'>','>','>','>',0,'>','>'}, {'<','<','<','<','<',0,'='} }; stack<char> op; stack<int> digit; int oper(int a, int b, char ch) { switch(ch) { case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/' : return a/b; } return 0; } int main() { string str; while(cin>>str) { mp['+'] = 0; mp['-'] = 1; mp['*'] = 2; mp['/'] = 3; mp['('] = 4; mp[')'] = 5; mp['='] = 6; int len = str.length(); op.push('='); int i = 0,j; while(i <= len && (str[i] != '=' || op.top() != '=')) { if(str[i] >= '0' && str[i] <= '9') { for( j = i+1; j < len; j++) { if(str[j] > '9' || str[j] <'0') break; } int m = 0; for(int k = i; k < j; k++) { m += (str[k] - '0')*pow(10,j - k-1); } digit.push(m); i = j; } else { switch(Precdede[mp[op.top()]][mp[str[i]]]) { case '<': op.push(str[i]); i++; break; case '=': op.pop(); i++; break; case '>': int a = digit.top(); digit.pop(); int b = digit.top(); digit.pop(); digit.push(oper(b,a,op.top())); op.pop(); break; } } } cout<<digit.top()<<endl; } return 0; }
表达式求值
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。