基本的思路是将中缀表达式转换为后缀表达式,消除括号,然后计算。后缀表达式又称逆波兰表达式。主要通过栈来实现。
中缀表达式转换为后缀表达式:
1.从左到右逐个扫描中缀表达式中的各项,遇到结束符“#” 转6,否则继续。这里选择想中追表达式中添加一个#或自行判断是否到字符串的末尾。
2.遇到操作数直接输出。
3.若遇到右括号 ,则连续出栈输出,直到遇到左括号为止。左括号出栈但不输出,遇到右括号也不输出。
4.若是其他操作符,则和栈顶操作符比较优先级,若小于等于栈顶操作符优先级,则连续出栈输出,直到大于栈顶操作符的优先级结束,操作符进栈。
5。
6.输出栈中剩余操作符,“#”除外。
这里我们将输入的一个表达式字符串转换为后缀,且输入表达式是正确无误的。
#include "Calculator.h"
int calculator::getPriorityInStack(char oper){
if(oper == '#')return 0;
else if(oper == '(')return 1;
else if(oper == '*' || oper == '/')return 5;
else if(oper == '+' || oper == '-')return 3;
else if(oper == ')')return 7;
return -1;
}
int calculator::getPriorityOutStack(char oper){
if(oper == '#')return 0;
else if(oper == '(')return 7;
else if(oper == '*' || oper == '/')return 4;
else if(oper == '+' || oper == '-')return 2;
else if(oper == ')')return 1;
return -1;
}
string calculator::changeToSuffix(string Prefix){
int isp,icp,i = -1 ;
string output = "";;
operstack.push('#');
while(++i < Prefix.length()){
isp = getPriorityOutStack( Prefix[i]) ;
if(isp == -1){
output+=Prefix[i];
output+=',';
}
else{
icp = getPriorityInStack( operstack.top() );
while(isp <= icp){
output += operstack.top();
operstack.pop();
icp = getPriorityInStack( operstack.top() );
output+=',';
}
operstack.push(Prefix[i]);
}
}
while (!operstack.empty())
{
output+= operstack.top();
operstack.pop();
output+=',';
}
return output.substr(0,output.length()-3);
}
使用 逗号,将数字分开。
c++中没有split函数,之后对改好的后缀表达式的运算就只能一个个遍历了。
后缀表达式的计算:
扫描表达式,遇到操作数进栈,遇到操作符,出栈两个操作数,然后使用操作符进行计算,先出栈的放在操作符的右边,获得结果进栈,知道遇到结束符。
int calculator::getResultBySuffix(string Suffix){
int i = 0;
string buff;
int a,b;
while( i < Suffix.length()){
if(Suffix[i] == ',')
i++;
buff = "";
while(Suffix[i] >='0' && Suffix[i]<='9'&& i <Suffix.length())
buff += Suffix[i++];
if(buff != ""){
numstack.push(atoi(buff.c_str()));
}else{
a = numstack.top();
numstack.pop();
b = numstack.top();
numstack.pop();
if(Suffix[i] == '+')
numstack.push(b+a);
else if(Suffix[i] == '-')
numstack.push(b-a);
else if(Suffix[i] == '*')
numstack.push(b*a);
else if(Suffix[i] == '/')
numstack.push(b/a);
i++;
}
}
i = numstack.top();
numstack.pop();
return i;
}
int calculator::getResult(string Prefix){
return getResultBySuffix(changeToSuffix(Prefix));
}
完成计算。
分享到:
相关推荐
Java算术表达式计算类库 ExpressionJ
Delphi 表达式计算控件formula最新版,支持很多数学函数,而且效率也很高
用C#实现的表达式计算引擎,支持词法分析,语法分析, 支持自定义关键字,自定义语法规则, 可以在项目里用来实现自定义逻辑计算。
java写的数学表达式计算程序,报告内含代码,能直接运行。
表达式计算是实现程序设计语言的基本问题之一,也是栈的应用的一个典型例子。设计一个程序,演示用算符优先法对算术表达式求值的过程。 【基本要求】 以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。...
基于算符优先算符的python开发的任意表达式计算求值类。 支持减号/负号,一符两用机制 支持浮点数、整数、字符串(用一个“开头,仿lisp语法) 支持所有算术运算符,包括**,//, % 支持全部7个比较运算符 支持与或非...
利用后缀表达式计算中缀表达式的值.数据结构 花费了我2周的时间才完成的 数据结构 c语言 MFC,是用MFC做的,,该程序功能强大,健壮性很强,对于错误输入有提示,程序完全正确,解压既可以运行
一个Java表达式计算类。帮助开发人员可以直接输入表达式。类中提供方法就可以得出运算结果输出。如输入:“3+5-2” 输出结果为:6
可以进行初步的表达式计算,是数据库课程的实例,自己编的哦,仅供参考用。
带括号的表达式计算,这是xoj上的一道题目 输入一个表达式如1+3*(4-3+8*7)计算它的值,用到了栈的技术
任意数学表达式计算源码 本文将从算法描述及编程思路,样例分析和注意事项等方面来阐述表达式计算的实现。
Write a program that reads an expression in a line as input and prints out the result. Only non-negative integers and operators below are allowed in the expression:+ - * / % ( )输入格式:A line of ...
表达式计算说明 很久就想编一个这样的计算器,只可惜一直没什么思路,最近突然灵感来了,所以就写下 这个程序。现在还在测试阶段,所以功能不是很完善。 程序功能:基本的表达式运算,可以自定义函数跟常量,...
中缀表达式计算C++实现
C语言表达式计算原代码详解,可进行+-*/等包括括号运算
Delphi表达式计算(用了这么多这个比较好) 还支持类似脚本的写法 同时也可以这样IIF(条件,A,B)
C#实现表达式计算的例子,支持变量。 如输入 1+2+3+(4*5) 输出:26 string[] key={"a","b","c"}; string[] val={"1","2","3"}; 输入:a+b+c 输出6
本文档是关于两种方式来实现表达式计算的!
一个简单实用的表达式计算类源码,用标准的C++写成,不用栈实现. 该源码在vc,c++ builder及GCC编译通过